100囚犯问题加强版与选择公理

《100囚犯问题加强版与选择公理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、100囚犯问题加强版与选择公理    在讲问题的加强版之前，让我们先来回忆一下经典的100囚犯问题（不是灯泡）。    100个囚犯从前往后坐成一列。坐在最后面的那个囚犯能够看到其余99个囚犯，坐在最前面的那个囚犯啥也看不见。看守给每个囚犯戴上一顶黑色的或者白色的帽子。然后，看守会从后往前依次叫这些囚犯猜测自己头顶上的帽子的颜色。如果哪个囚犯猜对了，他就自由了。坐在前面的每一个囚犯都可以听到后面的囚犯的猜测。如果这100个囚犯事先可以商量好一种策略，那么最理想的策略是什么？    囚犯们可以乱猜一通，最坏情况下所有人都猜错，平均下来则会有50个人猜对。这个题有趣的地方就在于，100

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

3、对。这不是最佳的策略。    不可思议的是，最佳策略可以保证，除了坐在最后面的囚犯以外，其余99个囚犯都能猜对。你能想出这样的策略是什么吗？继续看下去前不妨先想一下。    前面那种策略的问题在于，坐在最后面的那个人透露出的信息不多。他完全可以透露出与全局相关的一些信息，因此以后所有的人都可以用这条信息。比如，他可以数一数他前面99个人一共有多少顶白帽子，并约定他猜“黑”表示他前面共有偶数顶白帽，他猜“白”表示他前面共有奇数顶白帽。坐倒数第二的那个人也数一数他前面98个人的白帽子个数：如果他数出来的个数与先前透露出的个数一奇一偶，则他自己肯定戴的是白帽子；如果他数出来的和先前透露的

4、结果奇偶性相同，则他自己戴的肯定是黑帽子。这样，坐倒数第二的保证可以猜对了。那接下来咋办呢？不要忘了，其他囚犯能听到刚才那人猜的是什么，并且知道他的猜测保证是对的。这相当于每个人不仅能看到坐他前面的所有人的帽子颜色，还知道他背后那些人的帽子颜色，结合最初的那个奇偶性信息，接下来的每一个人都可以猜出自己脑袋上的帽子颜色。这样下去，至少99个囚犯可以保证被释放。这种策略显然是最佳的，不可能再有什么策略能保证所有人都被释放，因为至少坐最后的那个人不可能保证自己猜对。    真正有趣的东西来了。下面提出这个问题的加强版，囚犯的数目加强到无穷个！你将看到“无穷”这个神秘的东西再一次开始作怪。

5、无穷个囚犯面向数轴的正方向依次就座，第i个囚犯坐在数轴上坐标为i的地方，他可以看见所有坐标大于i的囚犯头顶上的帽子。看守给每个囚犯戴上黑色或白色的帽子，然后依次叫每个囚犯猜测自己头上的帽子颜色，猜对了的予以释放。另外一点和原来不同的是，囚犯们不能听到其他人的猜测。另外注意到，由于每个人前面都有无穷多个人，因此囚犯们无法通过数他前面的人数来判断出自己的位置，于是我们不得不加上一句：每个人都知道他后面有多少人（即他是第几个被问的）。同样地，事先所有囚犯可以商量出一个策略。你认为这下囚犯们还有什么好办法没？    这下囚犯已经不能通过自己的猜测来通风报信了，似乎每个人都只能瞎猜，任何人都

6、无法保证自己能猜对。你相信吗，居然有这样的策略，它可以保证除了有限个囚犯之外，其他囚犯全部释放！    考虑所有可能的颜色序列（你可以简单地想像成01串）。我们说两个颜色序列“无穷远相等”，如果经过了有限多项之后，余下的无穷多项完全相同（即存在某个数x，使得两个串在各自的第x位后面完全重合）。这种关系显然满足自反性、对称性和传递性，是一种等价关系。因此，按照这种有限位后对应相等的关系，我们可以把所有可能的颜色序列划分为一个个等价类。它们的交集为空（两个等价类如果有交集，由传递性它们立即并成了一个更大的等价类），并集为全集（若某序列不属于任何等价类，则它自己就是一个新的等价类），是全

7、集的一个划分。你能想象出一个等价类大致是什么样子的吗？假如把同一个等价类里的所有序列对齐并排放在一起，你从前往后走过去的时候会发现这些序列“越来越相像”。你走得越远，你会发现越来越多的序列开始变得互相重合；当你走到无穷远时，所有的序列都变成一个样了。    囚犯们事先在每一个等价类中选一个代表元，然后把所有等价类的代表元背下来。到时候，每个人都能够看到他前面无穷多个人的帽子颜色，并且知道他自己在整个序列的位置，于是能立即判断出他们现在所处的颜色序列在哪个等价类里。接下