Example 23 (8th US Mathematical Olympiad) A certain group has members , and there are three-person committees, none of which have exactly the same members. Prove: There exist two committees that have exactly one member in common.
Solution
Proof by contradiction. Assume that any two three-person committees either have two members in common or no members in common.
If committees and have members in common, then they have two common members and . If committee and also have (two) common members, then at least one of belongs to , thus and also have (two) common members. Therefore, committees with common members can be grouped together, such that within the same group, each committee has two common members, and committees from different groups have no common members.
The number of committees in each group must not exceed the number of members in that group . In fact, it is clear that . When , ; when , .
Suppose are two committees in the same group, then the other committees in this group can only be of the form , or , where has at most choices, so . Thus, the total number of committees the number of people , which is a contradiction.