MathLabs

第6题

在一次向参赛者提出 66 道题的数学竞赛中,任意两道题都有超过 25\frac25 的参赛者同时做出。此外,没有参赛者做出全部 66 道题。证明至少有 22 名参赛者恰好各自做出了 55 道题。
第 1/6 步:归约为一名 55 题解答者与 (n−1)(n-1) 名 44 题解答者
通俗地说

若存在至多一名 55 题解答者的反例,给其他人补加做出的题,直到第一名有 55 题、其余人都有 44 题,只会增加每个题对的解答人数,因此反例仍然成立且结构完全固定。

n=1+∑i=15ai+∑1≤i<j≤5bijn=1+\sum_{i=1}^5 a_i+\sum_{1\le i<j\le 5}b_{ij}
详细分析

反证假设至多有一名参赛者做出 55 题。给参赛者补加做出的题只会增加各题对的解答人数而不破坏任何条件,故不妨设有一名参赛者做出第 1,2,3,4,51,2,3,4,5 题(未做出第 66 题),其余每名参赛者都做出 44 题。在其余 n−1n-1 人中,设 aia_i(1≤i≤51\le i\le5)为未做出第 66 题与第 ii 题的人数,bijb_{ij}(1≤i<j≤51\le i<j\le5)为做出第 66 题但未做出第 i,ji,j 题的人数;则 n=1+∑i=15ai+∑1≤i<j≤5bijn=1+\sum_{i=1}^5 a_i+\sum_{1\le i<j\le5}b_{ij}。