100囚犯问题、100囚犯问题加强版与选择公理（上）

决定把较长的文章分段发布，不然大家读着太累。况且篇幅短一些的话，RSS输出也好看些:)

在讲问题的加强版之前，让我们先来回忆一下经典的100囚犯问题（不是灯泡）。

100个囚犯从前往后坐成一列。坐在最后面的那个囚犯能够看到其余99个囚犯，坐在最前面的那个囚犯啥也看不见。看守给每个囚犯戴上一顶黑色的或者白色的帽子。然后，看守会从后往前依次叫这些囚犯猜测自己头顶上的帽子的颜色。如果哪个囚犯猜对了，他就自由了。坐在前面的每一个囚犯都可以听到后面的囚犯的猜测。如果这100个囚犯事先可以商量好一种策略，那么最理想的策略是什么？

囚犯们可以乱猜一通，最坏情况下所有人都猜错，平均下来则会有50个人猜对。这个题有趣的地方就在于，100个囚犯事先可以商量一种策略，也就是说坐在后面的囚犯可以用他的猜测给坐在前面的囚犯透露一些信息。很显然，坐在最后面的囚犯是不可能保证自己猜对的，他猜黑猜白都只有一半的几率猜对，似乎没什么区别；但囚犯可以事先约定好一种暗号，即最后一个囚犯猜黑表示什么意思，猜白表示什么意思。比如，最后一个囚犯可以猜测和他前面的囚犯的帽子一样的颜色，这就相当于用他的猜测告诉了他前面那个囚犯该猜什么，于是坐倒数第二的囚犯可以保证被释放；此时，坐在倒数第三个位置上的囚犯面对与刚才坐最后的囚犯相同的处境，他同样可以用他的猜测提示出他前面那个人的帽子颜色。这样下去，可以保证至少50个人猜对，平均情况则有75个人猜对。这不是最佳的策略。

不可思议的是，最佳策略可以保证，除了坐在最后面的囚犯以外，其余99个囚犯都能猜对。你能想出这样的策略是什么吗？继续看下去前不妨先想一下。

前面那种策略的问题在于，坐在最后面的那个人透露出的信息不多。他完全可以透露出与全局相关的一些信息，因此以后所有的人都可以用这条信息。比如，他可以数一数他前面99个人一共有多少顶白帽子，并约定他猜“黑”表示他前面共有偶数顶白帽，他猜“白”表示他前面共有奇数顶白帽。坐倒数第二的那个人也数一数他前面98个人的白帽子个数：如果他数出来的个数与先前透露出的个数一奇一偶，则他自己肯定戴的是白帽子；如果他数出来的和先前透露的结果奇偶性相同，则他自己戴的肯定是黑帽子。这样，坐倒数第二的保证可以猜对了。那接下来咋办呢？不要忘了，其他囚犯能听到刚才那人猜的是什么，并且知道他的猜测保证是对的。这相当于每个人不仅能看到坐他前面的所有人的帽子颜色，还知道他背后那些人的帽子颜色，结合最初的那个奇偶性信息，接下来的每一个人都可以猜出自己脑袋上的帽子颜色。这样下去，至少99个囚犯可以保证被释放。这种策略显然是最佳的，不可能再有什么策略能保证所有人都被释放，因为至少坐最后的那个人不可能保证自己猜对。

真正有趣的东西来了。下面提出这个问题的加强版，囚犯的数目加强到无穷个！你将看到“无穷”这个神秘的东西再一次开始作怪。

最后报怨一句：刚才不小心看到莲蓬乳了