某次数学竞赛共有 $6$ 个试题，其中任意两个试题都被超过 $\dfrac{2}{5}$ 的参赛者答对了．但没有一个参赛者能答对所有的 $6$ 个试题．证明：至少有两个参赛者都恰好答对了 $5$ 个试题．（罗马尼亚）
【难度】
【出处】
2005年第46届IMO试题
【标注】
【答案】
略
【解析】
设有 $n$ 个参赛者，记为 $C_1,C_2,\cdots,C_n$，将 $6$ 个试题记为 $P_1,P_2,\cdots,P_6$，设
$S=\{(C_k;P_i,P_j)|1\leqslant k\leqslant n,q\leqslant i<j\leqslant 6,C_k同时答对了P_i 和 P_j \}$
下面我们考虑 $|S|$．
设 $P_i$ 和 $P_j(1\leqslant i<j\leqslant 6)$ 同时被 $x_{ij}$ 个参赛者答对，由题意，应有 $x_{ij}>\dfrac{2}{5}n$，从而 $x_{ij}\geqslant\dfrac{2n+1}{5}$，于是
$\displaystyle |S|=\sum\limits_{1\leqslant i<j\leqslant 6}x_{ij}\geqslant \sum_{1\leqslant i<j\leqslant 6}\dfrac{2n+1}{5}=C_6^2\cdot\dfrac{2n+1}{5}=6n+3$ ①
假设至多有一个参赛者恰好答对了 $5$ 个试题，由于没有一个参赛者能答对所有 $6$ 个试题，所以其他参赛者至多答对了 $4$ 个试题．设 $C_1,C_2,\cdots,C_n$ 分别答对了 $a_1,a_2,\cdots,a_n$ 个试题，不妨设 $5\geqslant a_1\geqslant a_2\geqslant\cdots\geqslant a_n\geqslant 0$．
若 $a_1\leqslant 4$，则 $a_k\leqslant 4(1\leqslant k\leqslant n)$，故 $\displaystyle |S|=\sum_{k=1}^nC^2_{a_k}\leqslant \sum^n_{k=1}C_4^2=6n$
与 ① 式矛盾．所以 $a_1=5,4\geqslant a_2\geqslant \cdots\geqslant a_n$．
显然，$n\geqslant 2$．若 $a_n\leqslant 3$，则
$|S|=\sum_{k=1}^nC_{a_k}^2\leqslant C_5^2+(n-2)C_4^2+C_3^2=6n+1$
与 ① 式矛盾．故 $a_n\geqslant 4$，从而 $a_2=a_3=\cdots=a_n=4$．
不妨设 $C_1$ 答对的 $5$ 个试题为 $P_1,P_2,\cdots,P_5$，设有 $b_j$ 个参赛者答对试题 $P_j(1\leqslant j\leqslant 6)$，则
$b_1+b_2+\cdots +b_6=a_1+a_2+\cdots+a_n=5+4(n-1)=4n+1$ ②
考虑 $\displaystyle \sum\limits_{j=2}^6x_{1j}\geqslant \sum_{j=2}^6\dfrac{2n+1}{5}=2n+1$ ③
由于有 $b_1$ 个参赛者答对试题 $P_1$，在这 $b_1$ 个参赛者中有一个共答对 $5$ 题，其余均答对 $4$ 题，故有
$\sum_{j=2}^6x_{1j}\geqslant 4+3(b_1-1)=3b_1+1$ ④
结合 ③④ 可得 $2n+1\leqslant 3b_1+1$，故 $b_1\geqslant\dfrac{2n}{3}$．同理可证
$b_k\geqslant\dfrac{2n}{3},k=1,2,3,4,5$ ⑤
完全类似地，考虑
$\displaystyle \sum\limits_{j=1}^5x_{j6}\geqslant \sum_{j=1}^5\dfrac{2n+1}{5}=2n+1$ ⑥
由于恰好有 $b_6$ 个参赛者答对试题 $P_6$，这 $b_6$ 个参赛者均只答对了 $4$ 个试题，故有
$\displaystyle \sum\limits_{j=1}^5x_{j6}=3b_6$ ⑦
结合 ⑥⑦ 可得，$3b_6\geqslant 2n+1$，所以
$b_6\geqslant\dfrac{2n+1}{3}$ ⑧
若 $n\not\equiv 0\pmod{3}$，则 $\dfrac{2n}{3}$ 不是整数，故由 ⑤ 知，$b_k>\dfrac{2n}{3}(1\leqslant k\leqslant 5)$
从而 $b_k\geqslant \dfrac{2n+1}{3}(1\leqslant k\leqslant 5)$ ⑨
结合 ⑧⑨ 可得 $b_1+b_2+\cdots+b_6\geqslant 6\cdot\dfrac{2n+1}{3}=4n+2$
与 ② 矛盾．所以 $n\equiv 0\pmod{3}$，从而由 ⑧ 式知 $b_6>\dfrac{2n}{3}$，而 $b_6$ 和 $\dfrac{2n}{3}$ 都是整数，所以
$b_6\geqslant\dfrac{2n}{3}+1$ ⑩
结合 ④ ⑩得
$b_1+b_2+\cdots+b_6\geqslant 5\cdot\dfrac{2n}{3}+\dfrac{2n}{3}+1=4n+1$ ⑪
由 ② 知，⑪式取等号，故 ⑤ 与⑩式均取等号，故有 $b_6=\dfrac{2n}{3}+1$．考虑
$\displaystyle \sum\limits_{1\leqslant i<j\leqslant 5}x_{ij}\geqslant\sum_{1\leqslant i<j\leqslant 5}\dfrac{2n+1}{5}=2(2n+1)=4n+2$ ⑫
由于有一个参赛者答对了试题 $P_1,P_2,\cdots,P_5$ 有 $b_6$ 个参赛者恰好答对了 $P_1,P_2,\cdots,P_5$ 中的 $3$ 个题，有 $n-1-b_6$ 个参赛者恰好答对 $P_1,P_2,\cdots,P_5$ 中的 $4$ 个题，故
$\displaystyle \sum\limits_{1\leqslant i<j\leqslant 5}x_{ij}=C_5^2+b_6\cdot C_3^2+(n-1-b_6)C_4^2=6n+4-3b_6=4n+1$
这与 ⑫式矛盾．
$S=\{(C_k;P_i,P_j)|1\leqslant k\leqslant n,q\leqslant i<j\leqslant 6,C_k同时答对了P_i 和 P_j \}$
下面我们考虑 $|S|$．
设 $P_i$ 和 $P_j(1\leqslant i<j\leqslant 6)$ 同时被 $x_{ij}$ 个参赛者答对，由题意，应有 $x_{ij}>\dfrac{2}{5}n$，从而 $x_{ij}\geqslant\dfrac{2n+1}{5}$，于是
$\displaystyle |S|=\sum\limits_{1\leqslant i<j\leqslant 6}x_{ij}\geqslant \sum_{1\leqslant i<j\leqslant 6}\dfrac{2n+1}{5}=C_6^2\cdot\dfrac{2n+1}{5}=6n+3$ ①
假设至多有一个参赛者恰好答对了 $5$ 个试题，由于没有一个参赛者能答对所有 $6$ 个试题，所以其他参赛者至多答对了 $4$ 个试题．设 $C_1,C_2,\cdots,C_n$ 分别答对了 $a_1,a_2,\cdots,a_n$ 个试题，不妨设 $5\geqslant a_1\geqslant a_2\geqslant\cdots\geqslant a_n\geqslant 0$．
若 $a_1\leqslant 4$，则 $a_k\leqslant 4(1\leqslant k\leqslant n)$，故 $\displaystyle |S|=\sum_{k=1}^nC^2_{a_k}\leqslant \sum^n_{k=1}C_4^2=6n$
与 ① 式矛盾．所以 $a_1=5,4\geqslant a_2\geqslant \cdots\geqslant a_n$．
显然，$n\geqslant 2$．若 $a_n\leqslant 3$，则
$|S|=\sum_{k=1}^nC_{a_k}^2\leqslant C_5^2+(n-2)C_4^2+C_3^2=6n+1$
与 ① 式矛盾．故 $a_n\geqslant 4$，从而 $a_2=a_3=\cdots=a_n=4$．
不妨设 $C_1$ 答对的 $5$ 个试题为 $P_1,P_2,\cdots,P_5$，设有 $b_j$ 个参赛者答对试题 $P_j(1\leqslant j\leqslant 6)$，则
$b_1+b_2+\cdots +b_6=a_1+a_2+\cdots+a_n=5+4(n-1)=4n+1$ ②
考虑 $\displaystyle \sum\limits_{j=2}^6x_{1j}\geqslant \sum_{j=2}^6\dfrac{2n+1}{5}=2n+1$ ③
由于有 $b_1$ 个参赛者答对试题 $P_1$，在这 $b_1$ 个参赛者中有一个共答对 $5$ 题，其余均答对 $4$ 题，故有
$\sum_{j=2}^6x_{1j}\geqslant 4+3(b_1-1)=3b_1+1$ ④
结合 ③④ 可得 $2n+1\leqslant 3b_1+1$，故 $b_1\geqslant\dfrac{2n}{3}$．同理可证
$b_k\geqslant\dfrac{2n}{3},k=1,2,3,4,5$ ⑤
完全类似地，考虑
$\displaystyle \sum\limits_{j=1}^5x_{j6}\geqslant \sum_{j=1}^5\dfrac{2n+1}{5}=2n+1$ ⑥
由于恰好有 $b_6$ 个参赛者答对试题 $P_6$，这 $b_6$ 个参赛者均只答对了 $4$ 个试题，故有
$\displaystyle \sum\limits_{j=1}^5x_{j6}=3b_6$ ⑦
结合 ⑥⑦ 可得，$3b_6\geqslant 2n+1$，所以
$b_6\geqslant\dfrac{2n+1}{3}$ ⑧
若 $n\not\equiv 0\pmod{3}$，则 $\dfrac{2n}{3}$ 不是整数，故由 ⑤ 知，$b_k>\dfrac{2n}{3}(1\leqslant k\leqslant 5)$
从而 $b_k\geqslant \dfrac{2n+1}{3}(1\leqslant k\leqslant 5)$ ⑨
结合 ⑧⑨ 可得 $b_1+b_2+\cdots+b_6\geqslant 6\cdot\dfrac{2n+1}{3}=4n+2$
与 ② 矛盾．所以 $n\equiv 0\pmod{3}$，从而由 ⑧ 式知 $b_6>\dfrac{2n}{3}$，而 $b_6$ 和 $\dfrac{2n}{3}$ 都是整数，所以
$b_6\geqslant\dfrac{2n}{3}+1$ ⑩
结合 ④ ⑩得
$b_1+b_2+\cdots+b_6\geqslant 5\cdot\dfrac{2n}{3}+\dfrac{2n}{3}+1=4n+1$ ⑪
由 ② 知，⑪式取等号，故 ⑤ 与⑩式均取等号，故有 $b_6=\dfrac{2n}{3}+1$．考虑
$\displaystyle \sum\limits_{1\leqslant i<j\leqslant 5}x_{ij}\geqslant\sum_{1\leqslant i<j\leqslant 5}\dfrac{2n+1}{5}=2(2n+1)=4n+2$ ⑫
由于有一个参赛者答对了试题 $P_1,P_2,\cdots,P_5$ 有 $b_6$ 个参赛者恰好答对了 $P_1,P_2,\cdots,P_5$ 中的 $3$ 个题，有 $n-1-b_6$ 个参赛者恰好答对 $P_1,P_2,\cdots,P_5$ 中的 $4$ 个题，故
$\displaystyle \sum\limits_{1\leqslant i<j\leqslant 5}x_{ij}=C_5^2+b_6\cdot C_3^2+(n-1-b_6)C_4^2=6n+4-3b_6=4n+1$
这与 ⑫式矛盾．
答案
解析
备注
