What should be proven, S=496?

PcelicaMaja wrote: What should be proven, S=496? I feel sorry for my fault. Now the question is corrected.

Any ideas?

Let's construct the incidence matrix of this situation, where $a_{i,j}$ denotes whether student $j$ is in the $i$th group. Note that given students $m$ and $n$, the number of clubs exactly one is in is given by $\sum_{k=1}^{10}(a_{k,m}-a_{k,n})^2$, so the square of this number is $(\sum_{k=1}^{10}(a_{k,m}-a_{k,n})^2)^2=\sum_{k=1}^{10}(a_{k,m}-a_{k,n})^4+2\sum_{1\le x<y\le 10}(a_{x,m}-a_{x,n})^2(a_{y,m}-a_{y,n})^2$. Now note that $\sum_{1\le m<n\le32}\sum_{k=1}^{10}(a_{k,m}-a_{k,n})^4=\sum_{k=1}^{10}\sum_{1\le m<n\le32}(a_{k,m}-a_{k,n})^4=10\cdot16^2=2560$. Also, $\sum_{1\le m<n\le32}\sum_{1\le x<y\le10}(a_{x,m}-a_{x,n})^2(a_{y,m}-a_{y,n})^2=\sum_{1\le x<y\le10}\sum_{1\le m<n\le32}(a_{x,m}-a_{x,n})^2(a_{y,m}-a_{y,n})^2$. Let $A_i$ be the set of students in the $i$th group. Suppose that $|A_x\cap A_y|=t$. Note that $\sum_{1\le m<n\le32}(a_{x,m}-a_{x,n})^2(a_{y,m}-a_{y,n})^2$ counts the number of pairs of students who differ in their membership in both groups $x$ and $y$. It is easy to see that this is just $t^2+(16-t)^2=2(t-8)^2+128$. Hence, the total interest-disparity of the class is $2560+2\sum_{1\le x<y\le10}(2(|A_x\cap A_y|-8)^2+128)=2560+2\cdot128\binom{10}2+2\sum_{1\le x<y\le10}(|A_x\cap A_y|-8)^2\ge14080$. In fact, $14080$ is the minimum possible value of the interest-disparity. Such a situation happens iff $|A_x\cap A_y|=8$ for all $1\le x<y\le10$. One such situation is below: 11111111111111110000000000000000 11111111000000001111111100000000 11111111000000000000000011111111 11110000111100001111000011110000 11110000000011111111000000001111 11001100110011001100110011001100 11000011110000111100001111000011 10101010101010101010101010101010 10011001100110011001100110011001 11001010100101100011010101101001 In fact, this can be done for much more than 10 groups.

This is a great problem involving swapping the order of summation! Let $A_i$ denote the set of groups student $i$ is in, then the answer is simply $$\sum_{i\le j} |A_i|^2+|A_j|^2 + 2 |A_i||A_j| +4 |A_i \cap A_j|^2 -4(|A_i|+|A_j|)(|A_i\cap A_j|)$$ Note the $|A_i|^2$ parts is simply $31\sum |A_i|^2$ since each of them is counted 31 times $\sum 2|A_i||A_j| = (\sum |A_i|)^2 - \sum |A_i|^2=25600-\sum |A_i|^2$. $\sum_{i\ne j} |A_i| |A_i \cap A_j|=\sum_i |A_i| \sum_{j\ne i }|A_i\cap A_j|$ $$ \sum_{j\ne i} |A_i\cap Aj|= \sum_{j\ne i} \sum_{i,j\in G} 1=\sum_{i\in G} \sum_{j\in G, j\ne i} 1= \sum_{i\in G} 15 = 15|A_i|$$ Therefore we have $25600-30\sum |A_i|^2 +4\sum|A_i \cap A_j|^2$ Let $g_i$ be the set of students in group $i$. Note $\sum |A_i|^2=\sum |A_i|+2\sum \binom{|Ai|}{2} = 160+2 $. #(group,group, student in both groups) $=160+2 \sum_{g_i, g_j} |g_i\cap g_j|$ Furthermore, $\sum |A_i\cap A_j|^2 = \sum |A_i\cap A_j| + 2\sum \binom{|A_i\cap A_j|}{2}=$ #(group, student, student) + 2#(group,group, student, student) where in all triplets/ quadruplets the student are in the group $=10\cdot \binom{16}{2} + 2\sum \binom{|g_i\cap g_j|}{2}$ Note the numbers cancel out (both 4800) so we are left with $25600+\sum_{i\ne j} -30|g_i\cap g_j| + 2(|g_i\cap g_j|)(|g_i\cap g_j|-1) \ge 25600-(90)(128)=14080$ as $f(x)=2x^2-32x \ge -128$. Construction: We want $|g_i\cap g_j|=8\forall i,j$. 11111111 11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 00000000 11111111 11110000 11110000 11110000 11110000 00111100 00111100 00111100 00111100 11001100 11001100 11001100 11001100 01100110 01100110 01100110 01100110 10101010 10101010 10101010 10101010 10100101 10100101 10100101 10100101 10010110 10010110 10010110 10010110