MathLabs

第6题

在一次向参赛者提出 66 道题的数学竞赛中,任意两道题都有超过 25\frac25 的参赛者同时做出。此外,没有参赛者做出全部 66 道题。证明至少有 22 名参赛者恰好各自做出了 55 道题。
第 3/6 步:十四个题对计数等于 kk,另一个等于 k+1k+1
通俗地说

这 1515 个整数题对计数都至少为 2n+15\frac{2n+1}{5},而它们的总和只比 15⋅2n+1515\cdot\frac{2n+1}{5} 大 11——因此 2n+15\frac{2n+1}{5} 本身必须是整数 kk,且其中十四个计数等于 kk,仅有一个等于 k+1k+1。

∑i=15ti+∑1≤i<j≤5tij=10+6(n−1)=6n+4=15⋅2n+15+1\sum_{i=1}^5 t_i+\sum_{1\le i<j\le 5}t_{ij}=10+6(n-1)=6n+4=15\cdot\frac{2n+1}{5}+1
详细分析

将全部 1515 个题对计数相加,相当于按每名参赛者统计其做出的题对数:那名 55 题解答者贡献 (52)=10\binom52=10 对,其余 n−1n-1 名 44 题解答者每人贡献 (42)=6\binom42=6 对,故 ∑ti+∑tij=10+6(n−1)=6n+4\sum t_i+\sum t_{ij}=10+6(n-1)=6n+4。另一方面,这 1515 个计数都是 ≥2n+15\ge\frac{2n+1}{5} 的整数,而 15⋅2n+15=6n+315\cdot\frac{2n+1}{5}=6n+3 仅比 6n+46n+4 少 11。若 2n+15\frac{2n+1}{5} 不是整数,则每个计数都 ≥2n+25\ge\frac{2n+2}{5},总和将 ≥6n+6\ge 6n+6,不可能;因此 k=2n+15k=\frac{2n+1}{5} 是整数,1515 个计数中有十四个等于 kk,剩下的一个等于 k+1k+1。