百囚猜帽

奇异果

某监狱里有100位囚犯，他们即将被执行死刑，但恰逢那天是国王的生日，国王打算给他们一次赦免的机会。

100位囚犯坐成一列，每人戴上一顶白色帽子或者黑色帽子。坐在最后面的囚犯能够看到前面99位囚犯所戴的帽子颜色，而坐在最前面的那位囚犯看不到其他人的帽子颜色。接着，看守会从后往前依次叫这些囚犯猜测自己头顶上的帽子颜色。如果哪位囚犯猜对了，他就自由了。对了，别人猜测的时候其他人都能听见。除此之外，一旦开始猜测，他们不可以有任何交流。

瞎猜？显然这是不可取的策略，因为每个人猜对的可能性只有二分之一，这太冒险了。于是，囚犯们聚集在一起商量策略，想办法让猜对的人数最多。

无从下手，尝试简化

假设现在只有囚犯A和B，A在第一个位置，而B在第二个位置。那么，他们可以使用这样的策略：B先猜A的帽子颜色，A听到B猜什么颜色就猜什么颜色。这样就能保证A的猜测是对的，不过B只有50%的概率猜对。

倘若增加到3位囚犯，我们看看有没有办法保证至少有2位囚犯猜对。

假设3位囚犯从前到后依次是A、B、C，C猜B的帽子顏色，然后B猜，而A收不到任何有用信息，他只能瞎猜，这样只能保证B是对的。显然，2位囚犯的策略已不再适用3位囚犯的情况，需要更换策略。可不可以根据奇偶性来进行猜测呢？

如果C看到A和B共有奇数顶白色帽子，就猜“白色”;如果C观察到A和B共有偶数顶白色帽子，就猜“黑色”。等C猜完后，那么B就知道他和A是有奇数顶白色帽子还是偶数顶白色帽子，然后他再看A戴的是白色帽子还是黑色帽子，就可以确定自己的帽子颜色了。对于A来说，他知道自己和B戴的白色帽子总数的奇偶性，也知道B戴的是白色帽子还是黑色帽子，那么他就能轻而易举地推测出自己头顶上的帽子颜色了。

从上面的分析中，我们知道该策略保证了A和B都能猜对自己头顶上的帽子颜色，而C有50%的概率猜对。

举实例，分步验证

理论上，根据颜色、帽子数量来猜测的策略是可行的。但将其运用到实际中，是否可行呢？我们来看看。

不妨假设3位囚犯和其所戴的帽子颜色如下表：

关于策略有这样的规则：

1.最后一位囚犯计算前面所有白色帽子的数量。如果是奇数，他就猜“白色”;如果是偶数，他就猜“黑色”。

2.除了最后一位囚犯，其他囚犯全部优先自保。

下面，囚犯们开始执行策略。

第三位囚犯，他看到了一顶白色帽子和一顶黑色帽子。也就是说，白色帽子数量为奇数，所以他猜“白色”。

第二位囚犯，他听到了“白色”，也就知道了白色帽子有奇数顶，而自己看到一顶白色帽子。所以，他知道自己头顶上的帽子为黑色，于是他猜“黑色”。

第一位囚犯，他知道了白色帽子有奇数顶，又听到第二位囚犯猜了“黑色”。所以，他知道自己头顶上的帽子为白色，于是他猜“白色”。

由上表可知，该策略能保证至少有2位囚犯猜对帽子颜色，也就是说策略可行。

人数增多，同样适用

人数增多，策略还是否适用呢？我们将这种策略推广到100位囚犯身上——如果最后一位囚犯看到前面所有囚犯有奇数顶白色帽子，就猜“白色”，否则猜“黑色”，然后前一位囚犯观察他前面的囚犯所戴白色帽子的数量，做减法就能知道自己头顶上的帽子颜色了，以此类推。

假设现在最后一位囚犯数出前面一共有52顶白色帽子，于是他猜“黑色”。没人知道他的帽子颜色，所以他只有50%的存活可能。但他猜的“黑色”却给前面的人提供了许多帮助。

到倒数第二位囚犯，他也数了前面98位囚犯戴的白色帽子的数量。如果数出偶数，他就猜“黑色”;如果数出奇数，他就猜“白色”。也就是说，如果倒数第二位囚犯数出前面有52顶白色帽子，那么他就能推出自己戴的是黑色帽子;如果他数出前面有51顶白色帽子，那么他就能推出自己戴的是白色帽子。这样他既救了自己，又为前面的人提供了可靠的信息，一举两得。

依次下去，至少99位囚犯可以被释放。这种策略显然是可行的，不过对于最后一位囚犯来说，他猜对猜错全靠运气了。