帽子谜题——一句“奇偶”救下 100 名囚犯里的 99 人

大家好，我是 Senko。本文将解读逻辑谜题的杰作“帽子谜题”。

100 名囚犯被排成一列，每人头上戴一顶红帽或蓝帽。各人能看见的只有排在自己前面的人的帽子，自己的帽子和后面的人的帽子都看不见。从队尾开始依次宣布自己帽子的颜色，答对释放，答错处决。若事先允许开作战会议，最多能确保救下几人呢？直觉上觉得能救一半就不错了，正解却是 99 人。而且用到的工具只有“奇数还是偶数”这一句话。

帽子谜题是什么

帽子谜题（英语 hat puzzle，这一版叫 prisoners and hats puzzle），是从他人的所见与发言中，推理出自己看不见的自身信息这一类逻辑谜题的总称。先把这次 100 人版的规则整理一下。

100 人排成一列，全员戴上红帽或蓝帽。颜色的构成自由（全员红帽也可能）
各人能看见的是排在自己前面所有人的帽子。自己和后面的都看不见
从队尾的人开始，依次只宣布“红”或“蓝”其中之一。宣布声全员都听得见
戴帽子之前，100 人可以商量作战

先想个朴素的作战。什么也不做的话，各人猜中自己帽子的概率是二分之一。100 人各赌各的，期望上只能救下 50 人。接着能想到的是“后面的人替前面的人报出颜色”这个作战。这样偶数位的 50 人必定获救，可当报信员的 50 人报的是与自己颜色无关的内容，还是听天由命。确定的仍是 50 人。我觉得这一带就是直觉的极限线。

答案是把全部信息压进第一句话

正解的作战是这样的。最先宣布的队尾囚犯，数一数自己看见的那 99 顶帽子，红帽是偶数就喊“红”，是奇数就喊“蓝”。事先作战会议上定的，就只有这一条约定。

站在第二名囚犯的立场想想。他看得见前方 98 人的帽子。假设第一句宣布是“红”，也就是“前方 99 人里的红是偶数顶”。若他亲眼数出前方 98 人的红是奇数顶，那么为了让奇偶对上账，他自己的帽子只可能是红。若是偶数顶，他就是蓝。这样第二名必定答对。

第三名往后也一样。各人只要把“最初宣布的奇偶”、“此后被宣布过的红的个数”和“自己看见的前方红的个数”这三样对一遍，自己的颜色就唯一确定了。因为前面的人依次都答对，听到的宣布全是真实颜色。从第二名到第一百名的 99 人，仅凭逻辑之力就全员必定获救。

可能牺牲的只有最初那一人，他的宣布是与自己颜色无关的信号，猜中概率仍是二分之一。也就是说，这个作战确保救下 99 人，期望值 99.5 人。这也能证明就是理论上限。因为最初那一人手里没有关于自己帽子的一丁点信息，任何作战都不可能保证 100 人全获救。

从三位贤者开始的归纳谜题谱系

帽子谜题自古就是被称作“归纳谜题”的这一族的招牌问题，其原型中有名的是三位贤者的故事。

国王让三位贤者闭上眼，告诉他们“给你们戴的是三顶红帽和两顶白帽中的某几顶”。实际上三人都是红帽。睁眼后贤者们看得见彼此的帽子，却看不见自己的。国王说“猜出自己颜色的人请报上来”，沉默持续了一阵之后，最聪明的那位贤者答出“我是红的”。

他的推理是这样。假如自己是白的，剩下两人看到的就是“一红一白”。那样的话，戴红帽那位贤者本可以推理出：“白帽只有两顶，把眼前这顶白的算上，如果我也是白的，另一人马上就会报出来。既然没人报，那我就是红的。”谁也答不上来的这份沉默，恰恰就是自己不是白帽的证据。从他人的无言中榨出信息这一手，后面会讲到的蓝眼睛岛谜题原样继承了下来。

而帽子谜题在 20 世纪末发生了戏剧性的进化。1998 年，计算机科学家托德·埃伯特在博士论文中发表的“帽子游戏”成了席卷数学界之外的流行，2001 年《纽约时报》甚至为它做了专题报道。

埃伯特的帽子游戏与纠错码

埃伯特版的规则乍看很简单。给三名玩家用抛硬币的方式戴上红帽或蓝帽。全员看得见彼此的帽子，看不见自己的。禁止商量，听信号同时宣布“红”“蓝”“弃权”三者之一。只要有一人猜中颜色，且无人猜错，团队就赢。全员弃权算输。

一人随便答、其余弃权的话胜率 50%。这看着像是极限，可正解的作战能达到75% 的胜率。作战是“若另外两人看着同色，就宣布相反的颜色；若看着不同色，就弃权”。

八种帽子组合里，三人全同色的只有两种。这时三人会全部宣布错误而输。可剩下六种里，只有戴少数派颜色的那一人开口，而且必定答对。也就是说，这个作战的本质在于：各人的正确率仍是二分之一、动不了，但把错误全都归拢到“三人同时答错的两种情形”，把正确稀释着分散到六种情形里。输的时候输得轰轰烈烈，赢的时候靠一人的声音安静地赢。这种偏置法把胜率推到了 75%。

令人吃惊的是，已知这个作战的一般化正是被称为汉明码的纠错码理论本身。玩家有七人时胜率可升到 87.5%，其最优策略在数学上与自动修复通信数据错误的编码设计是同一个东西。一道玩乐的谜题竟与最前沿的编码理论站在同一个擂台上，这项发现让这个问题出了名。

奇偶校验这套想法就在身边干活

100 人版的钥匙“奇数还是偶数”，在信息科学里被称为奇偶校验，其实每天都在支撑我们的生活。

信用卡号里含有一位用于检测输错的校验位。书籍的 ISBN、身份证号码也一样。存储的 RAID 通过把由多块硬盘内容算出的校验值单独存一份，做到哪怕整块硬盘坏掉，也能从其余部分复原内容。这与囚犯队伍里第一人喊出的信号，完全是同一个原理。

我觉得能从这道谜题带走的发想有两个。一个是“大家需要的信息，其实早已发到手里了”这个看法。100 名囚犯需要的信息是 100 份，可各人视野里已经映着 99 份，缺的只是整体的奇偶这区区一比特。在共享信息很多的团队里，该传达的不是全部，而只是差分。另一个是埃伯特游戏展示的个人的成绩与团队的成绩是两回事这个视角。一点也不提高各人的胜率，只靠设计失败如何重叠，就能提高团队的胜率。这通向的是把风险分散、还是刻意集中的资产组合设计式的发想。

颜色变多呢？同时宣布呢？

帽子颜色变成三种以上，作战会垮吗

不会垮。把奇偶换成给颜色编上 0、1、2 的号，把看见的号码之和除以 3 取余数让第一人宣布，后面全员就能用完全相同的道理算出自己的颜色。可能牺牲的只有第一人这点也不变。颜色有 k 种就把余数按 k 来算，两色的奇偶不过是它的特例——这一点很漂亮。

如果全员同时宣布呢

不能依次宣布的话，前面人的答案这个信息就用不上，99 人的保证便不可能了。不过有个有趣的变种：比如两人互看对方帽子并同时宣布时，只要约定“一人说与对方相同的颜色，另一人说与对方不同的颜色”，无论怎样配色都必定有一人答对。n 种颜色 n 个人时，用各人分担一个余数的类似作战，也能做到必定有一人猜中。就算全员答对做不到，至少一人答对是可以靠设计保证的。