Library / /15 of 48

, 2016

Combinatorics Difficulty 5.0 AIME Prove it Hong Kong

During a school year $44$ competitions were held. Exactly $7$ students won in each of the competitions. For any two competitions, there exists exactly $1$ student who won in both competitions. Is it true that there exists a student who won all of the competitions?

Solution

Yes. Consider any competition $C_1$ . Since every other competition shares a common winner with $C_1$ , there must be a winner of $C_1$ who won at least $\lfloor \frac{43}{7} \rfloor = 6$ more competitions by the pigeonhole principle. WLOG assume $A$ won the competitions $C_1, C_2, \dots, C_8$ .

Consider any other competition $C_k$ . By the pigeonhole principle, one of the winners of $C_k$ won at least $\lfloor \frac{8}{7} \rfloor = 1$ competitions among $C_1, C_2, \dots, C_8$ . But since the common winner of these competitions is $A$ , we know that $A$ won $C_k$ as well. Thus, $A$ won all the competitions.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.