一道经典的黑白帽子问题

一百个犯人纵向站成一排&＃xff0c;每人头上带上黑色或白色的帽子&＃xff0c;各人不知道自己帽子的颜色&＃xff0c;但是能看见自己前面所有人帽子的颜色。然后从最后边一个犯人开始&＃xff0c;每人只能大声说一个字&＃xff1a;“黑”或“白”&＃xff0c;保证其他人都能听到&＃xff08;但声音中不会附加任何其他信息&＃xff09;&＃xff0c;如果说中了自己帽子的颜色就存活&＃xff0c;说错了就拉出去枪决。在执行前&＃xff0c;允许所有犯人可以聚在一起商量策略。那么如果犯人都足够聪明不会犯错&＃xff0c;那么100个人最大的存活概率是多少&＃xff1f;

由于每个人看不到自己帽子的颜色&＃xff0c;所以必需有自己后面的人给自己提供有用的信息才可以存活。好在每个人都可以看到自己前面所有人的帽子颜色&＃xff0c;因此提供信息不难。但是尴尬的是&＃xff0c;如果提供给前面的人信息&＃xff0c;那么自己可能就活不了。同时&＃xff0c;在报自己颜色的时候&＃xff0c;又很难给别人提供信息。因此&＃xff0c;问题的关键是如何在报自己帽子颜色的时候&＃xff0c;又可以提供给前面的人以有用的信息&＃xff0c;这样才可以保证尽可能多的人活下来。
注&＃xff1a;为了讨论方便&＃xff0c;所有的顺序都是从后向前&＃xff0c;如“第1人”指的是整个一纵排的最后一人&＃xff0c;他可以看到前面所有人的帽子颜色。

最简单的办法&＃xff0c;就是每奇数位人报前一人帽子的颜色&＃xff0c;然后前一人再报自己的颜色&＃xff0c;以此类推&＃xff0c;直到排首。如&＃xff0c;第1人能看到第2人的颜色&＃xff0c;直接报出来告诉第2人&＃xff0c;这样第2人在报的时候直接报出来就可以存活&＃xff0c;但是第1个人因为报的是第2个人的帽子颜色&＃xff0c;所以只有50%的几率正好与自己的颜色一样。在这种情况下&＃xff0c;如果每对的颜色都是一样的&＃xff0c;那么100人全部存活&＃xff1b;反之&＃xff0c;如果每对颜色都不一样&＃xff0c;只有50人存活。
存活概率&＃xff1a;50人肯定存活&＃xff0c;另50人有一半的几率存活&＃xff0c;所以存活率为 (100% $\times$ 50 &＃43; 50% * 50 )/100 &＃61; 75%。

由于后面的人能够看到所有人的帽子的颜色&＃xff0c;所以我们可以利用这一点进行编码。我们很容易求出&＃xff0c;100 的二进制码为 ‭1100100 需要7位即可‬&＃xff0c;所以我们可以用最后面7个人进行编码对剩下93人的白帽子的数据进行表示。举例来说&＃xff0c;比如在前93人中有52顶白帽子&＃xff0c;其二进制编码为‭0110100&＃xff0c;那么最后7个人可以用黑表示1&＃xff0c;白表示0进行报颜色&＃xff0c;即 [白&＃xff0c;黑&＃xff0c;黑&＃xff0c;白&＃xff0c;黑&＃xff0c;白&＃xff0c;白]。当前面所有93人听到这个组合时&＃xff0c;根据之前商讨的约定&＃xff0c;就会明白有52顶白帽子。这是倒数第8人开始报颜色了&＃xff0c;虽然他看不见自己的颜色&＃xff0c;但是可以看到前面92人的帽子颜色&＃xff0c;由于已经知道了白色帽子的数量&＃xff0c;所以只要统计一下前面92人帽子的颜色即可推算出自己帽子的颜色&＃xff0c;比如数完白色帽子总数仍然是52&＃xff0c;自己肯定是黑色的&＃xff1b;反之如果白帽子变成51了&＃xff0c;自己则也是白帽子。以此类推&＃xff0c;直到最后一个人。&＃xff08;注&＃xff1a;题目设定所有犯人“足够聪明不会犯错”这点非常关键&＃xff09;。
存活概率&＃xff1a;此时93人肯定存活&＃xff0c;7人50%概率&＃xff0c;所以存活率为 (100% $\times$ 93 &＃43; 50% * 7 )/100 &＃61; 96.5%。

本解法利用奇偶性来解决&＃xff0c;可以将白帽子的奇偶性作为关键点来考虑。具体算法如下&＃xff1a;

1. 让第1人先统计前99人的白帽子的个数&＃xff0c;然后用黑表示奇数&＃xff0c;白表示偶数告知前面所有99人。
2. 下一人根据已经白帽子的奇偶性推算自己帽子的颜色&＃xff0c;如果奇偶性改变了&＃xff0c;则自己是白色&＃xff0c;否则是黑色。
3. 后面的人根据前人的颜色推断当前白帽子总数的奇偶性&＃xff0c;回到2&＃xff0c;直到所有人报完。

举例来说&＃xff0c;假设总共有52帽白帽子&＃xff0c;那么第1人会报白表示偶数。这样所有人都知道了有偶数顶的白帽子。第2人同样会统计前面98人的帽子&＃xff0c;如果总数是奇数&＃xff0c;白帽子总数的奇偶性由偶变奇了&＃xff0c;所以自己也是白色&＃xff0c;他报白即可。第3人听到第2人报白&＃xff0c;会将当前白帽子总数的奇偶性变成奇数&＃xff0c;然后继续进行报。
存活概率&＃xff1a;此时99人肯定存活&＃xff0c;1人50%概率&＃xff0c;所以存活率为 (100% $\times$ 99 &＃43; 50% * 1 )/100 &＃61; 99.5%。

以上三种算法的结果差异很明显&＃xff0c;尤其是最后一种&＃xff0c;几乎保证了所有人都可以存活。差异产生的根据原因在于报颜色的时候&＃xff0c;是否能够向前面的人提供有用的信息。第一种是每对间的信息完全是独立的&＃xff0c;除了前一人的黑白信息对后一人有用外&＃xff0c;对其他人完全无用&＃xff0c;所以存活率最低。第二种&＃xff0c;报颜色的同时还能够向后面所有人提供有用信息&＃xff0c;所以保证了93人的存活&＃xff0c;但是由于采用二进制的编码的方式&＃xff0c;多占用了7人进行编码。第三种方案利用奇偶性只用了1个人就可以向所有人提供了所必需的信息&＃xff0c;同时每个人在报的时候也向后面的人提供了有用信息&＃xff0c;信息的利用率最高&＃xff0c;所以让最多的人活了下来。第三种方案已经是最优解&＃xff0c;无法再优化了&＃xff0c;因为第1人是无论如何也不知道自己帽子颜色的&＃xff0c;只有50%的概率存活&＃xff0c;所以99.5%就是这个问题解的极限。