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

A certain organisation has n members and it has n+1 three member committees, no two of which have identical membership. Prove that there are 2 committees which share exactly one member.

MY ATTEMPT:

We have n members, which we can divide into n/3 three member groups. We can 'assign' one committee to each of these groups, leaving us with n/3 filled committees and (n+1-n/3) or 2n/3 - 1 completely empty committees. Now, if three of the filled committees were to share one member with one unfilled committee, we get one more filled committee, to fill all remaining committees in this manner we'd need 2n - 3 filled committees, which is more than the number of filled committees we have. I think the way to solve this is to consider those cases in which some committees share two members, but I don't know how to express that using equations. Help would be appreciated

• I have trouble with the first line. We don't know that $n$ is divisible by $3$. – saulspatz Mar 16 at 20:33

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.

One thing you can consider is actually trying to create these committees without having any two share one member. Create one committee at a time, making sure that it either shares 0 or 2 members with each of the existing committees. Additionally, note that in order to maximize the number of committees we can have, we will want to maximize the number of committees with 2 shared members. Let's try it:

The first committee: {1,2,3} (WLOG)

The second committee, going for 2 overlaps: {1,2,x} (WLOG); note that at this point, we have used 4 out of n individuals, and in order to maximize the amount of committees we can have under the given constraints, we should try to continue to make committees from the 4 we have already used without introducing new individuals into the mix, for as long as possible.

Third, Fourth: {2,3,x}, {1,3,x}

Notice now that each of these 4 committees shares 2 members with any of the other three, and that we have exhausted the 3-person committees that can be made with these four people. Additionally, note that any new committee we make must share no members with this group, or else we will now have two committees that share exactly one member***(see bottom for more thorough explanation). As we continue to keep making committees, we'll keep grouping individuals into groups of 4, then organizing these 4 individuals into their 4 possible committees of 3, until we have fewer than 4 individuals remaining. (If we do something other than this, we'll end up with fewer committees before we find ourselves forced to make a committee that shares exactly one member with an existing committee).

So if $$4|n$$, we will have created n such committees before we are forced to make the "n+1"th committee, which will have 1 member from an existing group of 4, forcing it to share exactly 1 member with an existing committee***.

If $$4|(n-1)$$ or $$4|(n-2)$$, we will have made n-1 or n-2 committees by this method, respectively, and our nth or "n-1"th committee must have either 1 or 2 members from an existing group of 4, forcing it to share exactly 1 member with an existing committee***.

If $$4|(n-3)$$, then we can create one more committee that doesn't share any members with existing groups of 4, but we will still only have n-2 total committees. We still have to create 3 more committees, and each of these will be forced to share either 1 or 2 members with an existing group of 4, making two committees that share exactly 1 member***.

***If a new committee shares all 3 members with a 4-person group (a group of 4 whose 4 possible committees all already exist), we will have a duplicate committee, a violation of the problem's conditions. If it shares 2 members (WLOG, 1,2) with a 4-person group, it will have exactly 1 member in common with each of the committees that is missing one of those 2 members (in this case, {2,3,x} and {1,3,x}). And if it shares 1 member with a 4-person group, it will obviously share exactly 1 member with another committee.