猫猫帽子谜题

前两天看到一道有意思的帽子谜题，分享一下。

题目

将十个人排成一行，主持人给他们每个人头上带上 黑色 或 白色 的帽子。他们每个人只能看到自己前面人的帽子颜色。主持人要求从最后一个人开始依次猜测自己头上的帽子颜色，至少要有 9 个人猜对自己头上的帽子颜色。

他们在开始之前可以交流商量策略，那么有什么策略能够满足要求呢？

虽然同样是帽子谜题，这可比「我不知道我的颜色」「我知道你不知道」「那我知道了」这种题目有意思多了。

提示

显而易见的一点是，第一个猜的人一定会被牺牲，也就是说后面的 9 个人都要能猜出自己的帽子颜色才行。

我的第一反应是：每个人告诉别人自己前面人他的帽子颜色不就行了？ 但实际上，这也正是这道题有趣的地方。

这个策略是不行的。

一个似乎矛盾的点是：

• 每个人只能提供 1 比特的信息，而每个人猜对也同样需要 1 比特，因此所有信息都必须派上用场；
• 除了第一个人，后面的人只能回答自己帽子的颜色，而自己帽子的颜色和下一个人帽子的颜色之间是无关的。

换句话说，后 9 个人只能提供 局域 的信息，他们提供的信息对别人没有帮助。因此，破局的点就是：

第一个人提供的信息应该是 全局 的，这样才能让后面所有人帽子的状态发生「纠缠」。

更进一步的提示

实际上，刚才我说的有一点小小的问题。如果我们的策略是成功的，那么每个人（除了第一个）通过听和看，都能知道其他 8 个人的帽子颜色，因此，这个谜题的本质是：

• 9 个人每个人带着一顶 黑色 或 白色 的帽子；
• 每个人都能知道其他 8 个人帽子的颜色；
• 某个上帝¹提供 1 比特的信息，让所有人都能猜对自己帽子的颜色。

再结合刚刚的分析，这 1 比特信息应该是用于描述 这 9 个人帽子的整体状态 的。这样一来，每个人就只需要回答

「其他人的帽子状态和上帝给出的总状态之间差了一顶什么颜色的帽子？」

就可以知道自己帽子的颜色了。

答案

因此，答案是？

新的问题

如果将题目中帽子的种类从两种变成三种，这道题还有解吗？

脚注

1. 也就是原题中的第一个人 ↩