某智力题的解题步骤

未分类

解题步骤

1、校长选定的数字序列之和记为S，则$S \bmod n$必然是一个唯一的整数$i$。

2、如果某个教授可以猜中这个$i$，是否能写对自己帽子上的数字？答案是：可以！因为，他只是不知道自己帽子上的$x$，而可以看到其他人的数字；然后$S = S' + x$，$S'$代表其他教授帽子上数字的和，$x$代表这位教授帽子上的数字；解同余方程$S' + x \equiv i \pmod{n}$，可以知道$x$。

3、但是，如何确保某个教授能猜中$i$呢？简单，因为$i$落在$0..n-1$中，现在有$n$位教授，让他们每个人猜一个$i$即可。准确来说，可以先给每一位教授一个从0到$n-1$的唯一编号，等校长写完数字，他们用自己的编号作为$i$，计算出$S'$，去解那个同余方程，得到$x$，那就是自己帽子上的数字。

4、以上分析表明，必然至少会有一位教授可以准确地猜出自己帽子上的数字。校长必输。