Old USAMO combinatorics problem about distribution of members into committees containing a fixed number of members.

Solution 1:

This can be done very slickly with linear algebra over $\mathbb F_2$, using a very similar argument to the famous "Clubs in Odd Town" puzzle. See this MSE question about Odd Town for some background.

Numbering the committees from $1$ to $n+1$ and the members from $1$ to $n$, associate to the $k^{th}$ committee a vector $v_k$ in $\mathbb F_2^n$, whose $i^{th}$ entry is $1$ if the $i^{th}$ person in that committee, and $0$ otherwise. Assume that no two committees share exactly one member. Since no two committees share $3$ members, either, this means that any two committees share an even number of members. In terms of the vectors, this means that $v_k\cdot v_h=0$ when $k\neq h$, while $v_k\cdot v_k=1$. This quickly implies that the committees are linearly independent; indeed, if we had $$ c_1v_1+c_2v_2+\dots+c_{n+1}v_{n+1}=0, $$ then taking the dot product of both sides with $v_k$ yields the equation $c_k=0$. This is true for all $k$, so the vectors are independent. This is a contradiction, as you cannot have $n+1$ linearly independent vectors in an $n$-dimensional vector space $\mathbb F_2^n$. Therefore, our assumption that no two committees share one member is false.