Suppose we have a town with $n$ residents who love forming groups. To limit the number of groups, the town head decided: 1) Every club must have an odd number of members, and 2) Any two clubs must share an even number of members. Show that it is not possible to form more than $n$ clubs.
There's a hint provided:
First try to find maximum number of subsets of the set $S=\{1,2,…,n\}$ so that for any two subsets $A_i$ and $A_j$ we have $|A_i\cap A_j|=k$. Now use and extend this idea.
I have no idea on how to prove the hint as well, and although the main problem and this hint look "similar", I cannot see a direct extension.
I tried the following way for the hint: Let subset $A_i$ be represented by a vector $v^i=(v_1,v_2,…,v_n)$ with $v_r=1$ if person $r$ is in that group and $0$ otherwise. Then $|A_i\cap A_j|=(v^i)'(v^j)=k$ for every $i\neq j$. So we want to find the number of possible $v^i$ such that $(v^i)'(v^i)\leq n$ for each $i$ and $(v^i)'(v^j)=k$ for each $i\neq j$.
I have no idea how to proceed. Can you help me with both the hint and the original question, please?
Best Answer
$1)$ Every club must have an odd number of members, and
$2)$ Any two clubs must share an even number of members.
Show that it is not possible to form more than $n$ clubs.
Let $C_1, C_2, \ldots, C_m$ be $m$ clubs satisfying $1)$ and $2)$.
For each $C_i$, let $x_i$ be its $(0,1)$-characteristic vector.
The characteristic vectors are a $n$-dimensional vectors, which components corresponds to a resident, and has value $1$ if he is in the club, and $0$ if not.
The dot product $x \cdot y$ of two of these vectors is the size of the intersection of the corresponding sets.
Rules $1)$ and $2)$ can now be written
$$ \begin{align} & 1) \: x_i \cdot x_i \:\: \text{is odd} \\ & 2) \: x_i \cdot x_j \:\: \text{is even}, \: \text{for} \: i \neq j \\ \end{align} $$
In modulo $2$
$$ \begin{align} & 1) \: x_i \cdot x_i = 1 \\ & 2) \: x_i \cdot x_j = 0, \:\: \text{for} \:\: i \neq j \\ \end{align} $$
If these vectors are linearly independent there can be at most $n$, since they are $n$-dimensional.
Suppose that for some scalars $c_1, c_2, \ldots, c_m$
$$c_1 x_1 + c_2 x_2 + ... + c_m x_m = 0$$
Now, for any $i$, take the dot product of both sides with $x_i$. Because of rule $2)$ everything cancels out, except for:
$$c_i x_i \cdot x_i = c_i = 0$$
Hence all the $c_i$'s are $0$, and the vectors are linearly independent, which proves the claim.