Maths Olympiad Prep

Library / /323 of 377

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

Somewhere in the universe, nn students are taking a 10-question math competition. Their collective performance is called laughable if, for some pair of questions, there exist 57 students such that either all of them answered both questions correctly or none of them answered both questions correctly. Compute the smallest nn such that the performance is necessarily laughable.

Solution

Solution:

Let ci,jc_{i, j} denote the number of students correctly answering questions ii and jj (1i<j101 \leq i < j \leq 10), and let wi,jw_{i, j} denote the number of students getting both questions wrong. An individual student answers kk questions correctly and 10k10-k questions incorrectly. This student answers (k2)\binom{k}{2} pairs of questions correctly and (10k2)\binom{10-k}{2} pairs of questions incorrectly. Now observe that
(k2)+(10k2)=k210k+45=(k5)2+2020 \binom{k}{2} + \binom{10-k}{2} = k^2 - 10k + 45 = (k-5)^2 + 20 \geq 20
Therefore,
1i<j10ci,j+wi,j20n \sum_{1 \leq i < j \leq 10} c_{i, j} + w_{i, j} \geq 20n
Now if the performance is not laughable, then ci,j56c_{i, j} \leq 56 and wi,j56w_{i, j} \leq 56 for all 1i<j101 \leq i < j \leq 10. Observe that there are 2(102)=902 \binom{10}{2} = 90 of these variables. Hence, in a boring performance,
20n1i<j10ci,j+wi,j9056=5040 20n \leq \sum_{1 \leq i < j \leq 10} c_{i, j} + w_{i, j} \leq 90 \cdot 56 = 5040
or n252n \leq 252. In particular this implies that if n253n \geq 253, the performance is laughable. This is the best bound because (105)=252\binom{10}{5} = 252, and if each of 252 students correctly answers a different 5-element subset of the 10 questions, then ci,j=wi,j=56c_{i, j} = w_{i, j} = 56 for all 1i<j101 \leq i < j \leq 10.

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.