Maths Olympiad Prep

Library / /449 of 520

Combinatorics Difficulty 6.1 National olympiad Prove it

Example 23 (8th US Mathematical Olympiad) A certain group has nn members (n5)(n \geqslant 5), and there are n+1n+1 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 AA and BB have members in common, then they have two common members aa and bb. If committee BB and CC also have (two) common members, then at least one of a,ba, b belongs to CC, thus CC and AA 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 kk must not exceed the number of members in that group hh. In fact, it is clear that h3h \geqslant 3. When h=3h=3, k=1hk=1 \leqslant h; when h4h \geqslant 4, k2k \geqslant 2.

Suppose {x,y,a},{x,y,b}\{x, y, a\},\{x, y, b\} are two committees in the same group, then the other committees in this group can only be of the form {x,a,b},{y,a,b}\{x, a, b\},\{y, a, b\}, or {x,y,d}\{x, y, d\}, where dd has at most h4h-4 choices, so k4+(h4)=hk \leqslant 4+(h-4)=h. Thus, the total number of committees n+1n+1 \leqslant the number of people nn, which is a contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.