Maths Olympiad Prep

Library / Harvard-MIT Mathematics Tournament /301 of 352

Harvard-MIT Mathematics Tournament

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 (1≤i<j≤101 \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 10−k10-k questions incorrectly. This student answers (k2)\binom{k}{2} pairs of questions correctly and (10−k2)\binom{10-k}{2} pairs of questions incorrectly. Now observe that
(k2)+(10−k2)=k2−10k+45=(k−5)2+20≥20 \binom{k}{2} + \binom{10-k}{2} = k^2 - 10k + 45 = (k-5)^2 + 20 \geq 20
Therefore,
∑1≤i<j≤10ci,j+wi,j≥20n \sum_{1 \leq i < j \leq 10} c_{i, j} + w_{i, j} \geq 20n
Now if the performance is not laughable, then ci,j≤56c_{i, j} \leq 56 and wi,j≤56w_{i, j} \leq 56 for all 1≤i<j≤101 \leq i < j \leq 10. Observe that there are 2(102)=902 \binom{10}{2} = 90 of these variables. Hence, in a boring performance,
20n≤∑1≤i<j≤10ci,j+wi,j≤90⋅56=5040 20n \leq \sum_{1 \leq i < j \leq 10} c_{i, j} + w_{i, j} \leq 90 \cdot 56 = 5040
or n≤252n \leq 252. In particular this implies that if n≥253n \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 1≤i<j≤101 \leq i < j \leq 10.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.