HMMT 二月 2006 · COMB 赛 · 第 10 题

HMMT February 2006 — COMB Round — Problem 10

Somewhere in the universe, n 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 n such that the performance is necessarily laughable.

解析

Somewhere in the universe, n 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 n such that the performance is necessarily laughable. Answer: 253 Solution: Let c denote the number of students correctly answering questions i and i,j j (1 ≤ i < j ≤ 10), and let w denote the number of students getting both questions i,j 4 wrong. An individual student answers k questions correctly and 10 − k questions ( ) ( ) k 10 − k incorrectly. This student answers pairs of questions correctly and pairs of 2 2 questions incorrectly. Now observe that ( ) ( ) k 10 − k 2 2

= k − 10 k + 45 = ( k − 5) + 20 ≥ 20 2 2 Therefore, ∑ c + w ≥ 20 n i,j i,j 1 ≤ i<j ≤ 10 Now if the performance is not laughable, then c ≤ 56 and w ≤ 56 for all 1 ≤ i,j i,j ( ) 10 i < j ≤ 10. Observe that there are 2 = 90 of these variables. Hence, in a boring 2 performance, ∑ 20 n ≤ c + w ≤ 90 · 56 = 5040 i,j i,j 1 ≤ i<j ≤ 10 or n ≤ 252. In particular this implies that if n ≥ 253, the performance is laughable. ( ) 10 This is the best bound because = 252, and if each of 252 students correctly 5 answers a different 5 element subset of the 10 questions, then c = w = 56 for all i,j i,j 1 ≤ i < j ≤ 10. 5