HMMT 二月 2006 · COMB 赛 · 第 10 题

英文解析

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, thereexist 57 students such that either all of them answered both questions correctly ornone 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 andi,jj (1 ≤ i < j ≤ 10), and let w denote the number of students getting both questionsi,jwrong. An individual student answers k questions correctly and 10 − k questions 4
    ( ) ( )
    k 10 − kincorrectly. 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 ni,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
    ( )
    i < j ≤ 10. Observe that there are 2 = 90 of these variables. Hence, in a boring 10
    performance,2
    ∑
    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.
    ( )
    This is the best bound because = 252, and if each of 252 students correctly 10
    answers a different 5 element subset of the 10 questions, then c = w = 56 for all 5
    i,j i,j
    1 ≤ i < j ≤ 10. 5