3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Any help, anybody? $\endgroup$ – Landon Carter May 5 '16 at 17:32
  • $\begingroup$ Assuming club=group, here's a dumb question: If we have n+1 clubs and n residents, how would we have that every club must have an odd number of members? If we have 1 resident per club, then 1 club has 0 members and hence an even number. Same thing I think for n+2 and so on. $\endgroup$ – BCLC May 5 '16 at 17:35
  • $\begingroup$ You need to find "minimum" number of groups. That's why the story has been given: people love to form groups but the headman limits the no. of groups to be formed. $\endgroup$ – Landon Carter May 5 '16 at 17:55
  • $\begingroup$ Landon Carter, I don't follow. What do you mean exactly? Also, I'm not sure you answered my dumb question $\endgroup$ – BCLC May 7 '16 at 9:33
2
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ This method is quite common and standard, it seems. Can you please cite a reference to learn this? $\endgroup$ – Landon Carter May 8 '16 at 16:59
  • $\begingroup$ Linear Algebra methods in Combinatorics by Babai $\endgroup$ – JKnecht May 8 '16 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.