Title

$40$ 个学生,每个学生在黑板上写上两个数,且任意两个学生写的数中至少有一个是相同的,试证:至少有一个数,在黑板上出现了 $27$ 次。

Proof

假设每两个学生写的两个数都是相同的:

那么这两个数各出现了 $40$ 次,命题显然成立。

假设每两个学生写的两个数不一定完全相同:

那么我们一定可以找到两个学生:甲和乙,并且假定甲写的两个数是 $A$$C$,乙写下的两个数是 $B$$C$.

此时我们注意到这样一个结论,如下所述

结论

对于除甲乙外的第三名学生,他写下的数中如果包含一个 $A$, $B$, $C$ 之外的数,那么他所写下两数中的另一个数必定是 $C$

结论的证明很容易:首先,这第三名学生写下的数不可能和 $\{A,B,C\}$ 完全没有交集;其次,另一个数不能是 $A$, 否则就和乙没有公共数,也不能是 $B$, 否则就和甲没有公共数。

此时我们可以对除甲乙外的其他学生进行分类:

  1. 个性者:若该学生写下的两个数中包含(恰好)一个 $A$, $B$, $C$ 之外的数,那么称这位学生为 “个性者”

  2. 默契者:若该学生写下的两个数是 $\{A,B,C\}$ 中的某两个,那么称这位学生为 “默契者”

于是继续我们的证明:

  1. 剩下的学生中存在个性者:

    不妨记其名字为

    • 由前面的结论可以得知,所有的个性者,包括丙自身在内,每个人写下的数中都包括 $C$

    • 同时,对于默契者,他们写下的数也必须包括 $C$;如若不然,则和丙同学没有共同数

    所以,这种情形下,每一个人写下的数中都包括 $C$,从而此数出现了 $40$ 次,命题自然成立。

  2. 剩下的学生中不存在个性者:

    那么,剩下的所有学生都是默契者,他们写的数具体是什么也不存在任何限制;

    剩下的 $38$ 名学生一共写了 $38 \times 2 = 76$ 个数,这些数只能是 $A$, $B$ 或者 $C$,因此$\{A,B,C\}$ 中的某一个至少出现了 $\lceil \frac{76}{3} \rceil = 26$ 次,再算上甲乙的贡献,这个数至少出现了 $27$

综上所述,命题得证。

Q.E.D.