奇异果
某监狱里有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戴的是白色帽子还是黑色帽子,就可以确定自己的帽子颜色了。……