题目

数学大臣尤泽尔被国王亚路开德召到皇宫，却发现前面已经排了 9 个非常奇怪的人——这些人全都戴上了帽子，或黑或白。

早在一旁等候的侍卫克里亚，向一脸疑惑的尤泽尔走了过来。

“陛下正在让他们完成一个挑战”，克里亚解释说，“每次我都会给他们每个人随机戴上黑或白色的帽子，所有人要轮流猜自己头顶上的帽子的颜色，最多只可以猜错一次。”

“原来这些帽子不是他们自己戴上的？但陛下恐怕要失望了，很显然人类无法看到自己的头顶”，尤泽尔略加思索，“除非里面有数学大臣。”

“数学大臣就可以看到头顶吗？”

尤泽尔加入了挑战。

他们有一次商讨策略的机会，可以按任意顺序排队和报答案，但在排好队之后尤泽尔才会开始给他们戴帽子，排好队后只有嘴可以动。请问他们有完成挑战的方法吗？

答案（不唯一）

由于每个人都看得到前面的人的帽子，也听得到其他人报答案，所以以下策略是可行的：

• 每个人都面朝前方排成一条直线，并从后往前报答案
• 对于最后一个人，若前面有奇数顶黑帽子，就报黑色，若有偶数顶黑帽子，就报白色
• 对于其他人，根据后面的人报的颜色可以推算出自己的颜色

证明

由于每个人都看得到前面的人的帽子，也听得到其他人报答案，所以除了最后一个人以外，其他人：

• 可以看到前面有多少顶黑帽子
• 可以听到除了最后一个人，后面有多少顶黑帽子
• 最后一个人报出了前 9 个人共有奇数还是偶数顶黑帽子

不妨设总共有偶数顶黑帽子，否则就将颜色取反，此时有：

• 若前面有偶数顶，后面有偶数顶，那么自己一定是白帽子
• 若前面有偶数顶，后面有奇数顶，那么自己一定是黑帽子
• 若前面有奇数顶，后面有偶数顶，那么自己一定是黑帽子
• 若前面有奇数顶，后面有奇数顶，那么自己一定是白帽子

上述推理很好证明，以第一点为例：若前面有偶数顶，后面有偶数顶，如果自己还是黑帽子的话就总共有“前面偶数顶+后面偶数顶+自己1顶=奇数顶”了，与总共有偶数顶黑帽子矛盾，所以自己一定是白帽子。

其他三点证明也同理。因此该策略可以保证除了最后一个人以外必定猜对，可以完成挑战。

原理

原理在证明中已经体现得淋漓尽致了，就是奇偶性，然后舍弃最后一个人来传递信息，再充分利用游戏规则中隐含的已知信息来推算答案。

更深层的原理其实类似于本系列第一题的结论：在所有数值域均为模数的情况下，模意义下减法具有唯一解。

我们可以这么表述这个答案：设 $c_i$ 为从前往后第 $i$ 个人帽子的颜色，$0$ 为白色，$1$ 为黑色，这样从后往前报颜色，那么第 $i$ 个人：

• 可以看到前面的颜色和：$s_1=c_1+c_2+\cdots+c_{i-1}$
• 可以听到后面的颜色和：$s_2=c_{i+1}+c_{i+2}+\cdots+c_9$
• 最后一个人报了总颜色和：$s=c_1+c_2+\cdots+c_9$

因此自然可以算出自己的颜色 $c_i=s-s_1-s_2$。上式全部是模 $2$ 意义下的，根据上述结论，$c_i$ 有唯一解。

当然，我们其实也可以将上述操作看作异或，这是另一种解释。

思考

可以更多人吗？

显然可以，因为上述策略总是可以保证除了最后一个人以外全对，因此无论有多少个人都可以完成挑战。

可以更多颜色吗？

也可以，因为该结论在任意模数下都是成立的，因此这个策略可以推广到任意颜色数

其他的答案？

在理解以上答案之后，我们不禁思考能否选择观察别的数据或别的性质。

毫无疑问，由于最后一个人已知信息最多，但唯独绝对不可能知道自己的信息，因此最后一个人一定是负责报一个全局信息来让其他人能够猜出自己颜色的。

什么样的信息符合要求呢？思考上述过程，我们发现要求是：对于任意已有的颜色序列，再加入不同的颜色会对信息造成不同的变化（不变也算作一种变化），且这一运算是存在逆运算的，且这一信息的可能状态数不超过颜色个数。

先只考虑两个颜色的情况，此时我们需要用一个 bit 来表示出包含所有人颜色在内的信息。

我绞尽脑汁想出来一个“长度为奇数的黑色段的奇偶性”，这是可行的，但其本质上其实与之前一个答案是一样的，因为黑帽子总数的奇偶性就取决于长度为奇数的黑色段的奇偶性，因此实际上是换一个表述。

还有其他的表述形式，例如“黑色与白色个数的差值（若 $n$ 为奇数还需要减去 $1$）是否是 $4$ 的倍数”、“黑色连续段的长度的异或和的奇偶性”，这些其实都等价于黑帽子个数的奇偶性。

实际上，对于每个人都是已知除了自己与最后一个人以外的所有颜色信息，所以我们只需要满足，在其他信息相同的情况下，自己是黑是白会导致全局信息不同即可。

用数学来描述的话，这样的全局信息必须对应一个函数 $f: {B,W}^{n-1} \to {0,1}$，使得对于每个位置 $i$ 和每个其他帽子的配置，改变第 $i$ 顶帽子的颜色都会改变函数值 $f$。

满足这种条件的函数，只能是前 $n-1$ 顶帽子黑帽子个数的奇偶性函数或其否定（即奇偶性的补）。

因此，唯一可行的策略就是基于奇偶性的策略，不存在其他策略能保证最多错一次。

附录

参考文献

由于这个问题非常经典，解法也非常经典，所以就写到这了。

版权信息

本文原载于 reincarnatey.net，遵循 CC BY-NC-SA 4.0 协议，复制请保留原文出处。