MathLabs

第6题

在一次向参赛者提出 66 道题的数学竞赛中,任意两道题都有超过 25\frac25 的参赛者同时做出。此外,没有参赛者做出全部 66 道题。证明至少有 22 名参赛者恰好各自做出了 55 道题。
第 6/6 步:选取避开唯一 (k+1)(k+1) 项的分拆
通俗地说

对于给定的分拆 {a,b,c}∪{d,e}\{a,b,c\}\cup\{d,e\},同余式中只出现十五个 tt 中的七个,因此总能选取分拆使这七个全都等于 kk——于是同余式变为 k≡1+6k(mod3)k\equiv 1+6k\pmod3,即 0≡1(mod3)0\equiv1\pmod3。

k≡1+6k(mod3) ⟹ 1≡0(mod3)(contradiction)k\equiv 1+6k\pmod 3\ \Longrightarrow\ 1\equiv 0\pmod 3\quad(\text{contradiction})
详细分析

由第3步,十五个 tt 中有十四个等于 kk,只有一个等于 k+1k+1。若这个例外的 (k+1)(k+1) 项是某个 tet_e,取 {a,b,c}⊂{1,2,3,4,5}∖{e}\{a,b,c\}\subset\{1,2,3,4,5\}\setminus\{e\},并令 dd 为剩下的下标;若例外项是某个 txyt_{xy},则选取 {a,b,c}\{a,b,c\} 使 {x,y}\{x,y\} 既不是 {d,e}\{d,e\} 也不是 {a,b,c}\{a,b,c\} 的子集(即令 x∈{a,b,c}x\in\{a,b,c\} 且 y∈{d,e}y\in\{d,e\})。无论哪种情形,例外项都不会出现在 tde,ta,tb,tc,tab,tbc,tcat_{de},t_a,t_b,t_c,t_{ab},t_{bc},t_{ca} 之中,故这七项全都等于 kk。由第5步即得 k≡1+6k(mod3)k\equiv 1+6k\pmod3,即 0≡1(mod3)0\equiv1\pmod3,矛盾。因此至少有 22 名参赛者做出了 55 道题。