100个囚犯和灯泡的那些事儿
说有 100 个囚犯分别关在 100 间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。初始时，灯是关着的。看守每次随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢？
这个经典的问题在网上转载无数，题目描述被好事者们改得天花乱坠，甚至加进了“这盏灯永远有充足的能源供应”、“如果灯泡坏了或是电路出了故障会马上修好”等条件，剥掉了“算法问题”的外壳，填补了本不存在的漏洞，让更多的人动起了脑筋。在论坛上，每次贴出这个问题，总会引起一大人的口水战。但很不幸的是，这个题目的来源至今仍是个谜。据目前的已知情况推测，这个题目最早来源于 Berkeley 的电气工程荣誉学会，时间大概是 2001 年。在 2002 年的 7 月， IBM 的 Ponder This 趣题栏目介绍这个题目，囚犯与灯泡一炮走红，随即遍布网络的各个角落。 2003 年， The Mathematical Intelligencer 杂志上发表了一篇题为 One hundred prisoners and a lightbulb 的论文，也让囚犯们正式引起了数学家们的关注。
相信这个问题的答案大家已经非常熟悉了，不过这里我想用另一种更玄乎的、更具启发性的方式重新讲述一下答案。
不妨幻想房间中有一个盒子，盒子里可以容纳一个小球。灯泡亮就表示这个假想的盒子里有一个假想的小球，灯泡不亮就表示这个假想的盒子是空的。因此，用开关控制灯泡就相当于在盒子里放进小球或者取走小球。初始时，每个囚犯手中都有一个小球（当然这个小球也是囚犯们自己意淫出来的）。游戏开始前，囚犯们选择一个代表作为统计者。之后，每次有囚犯进入房间后，如果小球还在他手里，盒子恰恰又是空着的，他就把小球放进去；而统计者的任务就是收集小球——每次进入房间后，看到盒子里有小球就把它拿走。如果某个时刻统计者手中集齐了（包括它自己的） 100 个小球，就说明所有人都进过房间了。
这个简单而巧妙的协议让人大为折服。然而，对这个问题的讨论并未结束，计算协议完成所需的期望时间、设计期望时间更短的协议，这都是非常有挑战性的问题，虽然它们已经背离了这个问题的初衷——协议的设计。这篇论文里详细总结了著名数学趣题论坛 [wu::forums] 上的牛人们对上述问题的探索。不过，即使回到协议设计的话题上，这个题目也还有戏可唱。
现在，让我们来考虑这个问题的一个加强版。上述策略能成功的原因是，大家都知道房间里的灯泡一开始是不亮的（盒子里一开始没有小球）。如果灯泡的初始状态并不确定，那就麻烦了：统计者收集了 100 个小球并不足以说明所有
人都来过房间，而他有可能永远也等不到第 101 个小球。那么，这个问题还有解吗？在继续想下去之前，你不妨先思考一下。
是的，这个问题仍然有解，而且办法和原来几乎一样，只是有一些非常巧妙的变通。此时，“小球模型”开始发挥作用了：在引入了一些更加复杂的因素后，比起开灯关灯，用“小球语言”来描述显得更直观易懂。
囚犯们仍然选出一个统计者，由他来完成收集小球的任务。只不过这一次，每个囚犯初始时都有两个（假想的）小球。每个囚犯来到房间后，如果发现盒子是空的，手中正好还有小球的话，他就在盒子里放一个小球。统计者仍然只负责把小球从盒子里取出来。什么时候统计者收集到了200个小球（包括自己的两个），他就知道所有人都来过了，因为如果还有人没进房间，他最多只能拿到 198 + 1 个小球。注意，这 200 个小球可能就是囚犯手中的 200 个小球，也有可能是囚犯手中的 199 个小球加上初始时房间里的小球。体会一下这个协议如何巧妙地解决了房间初始状态不确定的难题，真是越想越有味道。
还不过瘾吗？现在与大家分享一个更强的加强版。
在以上协议中，只有一个人能知道所有人都来过房间。是否存在一个协议，使得最终可以产生两个人，他们都知道所有人都进过房间？如果存在这样的协议，给出一个来；如果不存在，证明之。为了方便思考，你可以暂时假设初始时房间的灯泡不亮。
不要轻易就认定这是不可能的。至少当 n = 2时，这样的协议明显存在！
即使灯泡的初始状态不定，当 n=2 时，两个人也能保证都知道对方进过房间。假设双方手中各有两个球，囚犯 A 总是试图把自己的小球放进盒子，囚犯 B 总是试图把小球取走。如果 B 拿到了 4 个小球，他就知道了 A 一定来过房间；而只要 A 放好的小球被拿走了， A 也知道 B 进过了房间。
但是，当 n>2 时，不存在这样的协议，使得有两个人都能获知所有人都已进过房间。 Peter Winkler 的 Mathematical Puzzles: A Connoisseur's Collection 一书中给出了这个结论的一个大致证明思路。
让我们考虑其中任何一个囚犯。我们假设他的策略是确定性的，他的下一步行动完全取决于之前看到的状态序列。假设在某一步，他看到的状态和上次离开房间时的状态相同，但他选择了改变状态。这时，你可以质问他，那你为啥不在上次就把状态改过来，偏偏要这次才去扳开关呢？看守完全有可能连续两次都是叫你进的房间，这样你不就浪费了一次进房间的机会了吗？因此，我们可以假设，当他进入房间时看见的状态和上次走的时候一样，他是不会去扳动开关的。
接下来，让我们假设在某一步，这个囚犯的策略是“不动开关，保留原状态”。那么，我们可以认为他以后就再也不会动那个开关了！因为在最坏情况下，他根本没有改变灯泡状态的机会！具体地说，若无视掉这个囚犯以后的行动，今后的房间状态序列里必然有一种状态将出现无穷多次，比方说状态“开”出现了无穷多次吧。那么在最坏的情况下，这个囚犯从此开始总是在开灯的时候进屋。
而他在这一步没有变动开关，并且以后的每一步里他所看到的状态都将和上次看到的一样，因此以后他
都不会变动开关了。
因此，这名囚犯首次进入房间时的策略绝不可能是“不动开关”，因为这样他以后可能都没机会动开关了，没人会知道他来过房间。如果他的策略是“如果灯开着，就把它关掉”，那么由第一个引理，今后他看见关灯状态都不会去改变状态了，直到下次见到灯亮时才会有所行动。每次见到灯亮时，他有两种选择，把灯关掉，或者让它接着亮。如果选择关灯，他又要等到下次灯亮才会行动；如果不关灯的话，相当于他这次没做任何操作，今后就再也没法行动了。也就是说，他的整个策略无非是“关过多少多少次灯之后就不管了”。类似地，如果他首次进入房间时的策略是“如果灯关着，就把它打开”，同理可知他今后的策略限制在了“再开几次灯就不开了”。当然，首次进入房间的策略还可能是“无论状态如何，总是扳动开关”，不过实际情况一揭晓，他的策略也就立即归为了上述两种情况中的一种。
换句话说，每个人的策略都无外乎两种：只负责开 x 次灯，或者只负责关 x 次灯。当然，如果所有人都只开灯不关灯（或者只关灯不开灯），肯定是一点用处都没有。因此，无妨假设囚犯 A 负责开灯，囚犯 B 负责关灯。如果囚犯 C 也只负责开灯， A 永远不能分辨出 B 、 C 究竟是都完成了协议，还是都差最后一步；如果囚犯 C 只负责关灯， B 就成了那个被蒙在鼓里的人了。
少了你的房间也就是说，整个问题的唯一解法就是，其中一个人只负责关灯，另外所有人只负责开灯；或者其中一个人只负责开灯，另外所有人都只关灯。换句话说，我们的“统计者协议”其实是唯一的解法。
在 Mathematical Puzzles: A Connoisseur's Collection 一书中，我们有幸看到了这个问题的另一个更加有趣的变种，让囚犯们的难题继续活跃着人们的大脑。
还是 100 个囚犯，还是一个空房间，还是要求所有囚犯事先构造一个协议，能保证有人可以断定出所有人都来过房间。不过，这次不同的是，房间里有两个灯泡，分别由两个开关来控制（不妨假设初始时他们都是不亮的）。大家估计要说了，一个灯泡都能解决的事儿，用两个灯泡还不容易？嘿嘿，这次有一个附加的要求：所有人都必须遵循同一套策略。
这些智力游戏不仅仅是思维的体操，它竟然有不少让人意想不到的实际应用。远在这个智力题诞生之前，就有一个几乎等价的分布式计算难题困扰着人们：假如一个程序有 n 个进程，它们操作的是同一段（不太宽裕的）公共内存。但在程序运行中，有些进程可能会崩溃掉。我们希望程序能报告出当前还有多少个进程在工作，但使用的空间越少越好。一个简单的解决方案就是，预先指定一个进程作为统计者，照搬囚犯们的策略，只消一个 bit 即可统计出活动进程的大致数量。但问题是——这个统计进程崩溃了咋办？因此，为了避免有关键进程崩溃，这些进程的行为必须得一致才行。 1990 年， Michael J. Fischer 、 Shlomo Moran 、 Steven Rudich 、 Gadi Taubenfeld 四位牛人共同发表了一篇叫做 The Wakeup Problem 的论文，提出了著名的跷跷板协议 (see-saw protocol) ，成功解决了这一难题。
我们还是把其中一个开关想象成一个盒子，它里面只能放一个小球。再把另一个开关想像成一个跷跷板，
它也只有两种状态：左低右高、左高右低。要想改变跷跷板的倾斜方向，只能扳动它的开关。初始时，每个囚犯手中都有一个（假想的）小球。每个囚犯第一次进入房间后，他都幻想自己坐到跷跷板低的那一边上，然后把自己这一侧扳高。以后每次回到这个房间时，他都看看自己所在的那一侧是高还是低：如果是低的话，他就取走盒子里的小球（如果有的话），于是手中就多了一个小球；如果是高的话，他就在盒子里放一个小球（如果盒子是空的），此时手中的小球就少了一个。注意，如果他把手中的最后一个小球放进盒子了（此时他手中没有小球了），他就必须从跷跷板上下来，把自己所在的那一侧扳低，之后就再也不进行任何操作了。如果有某个囚犯收集到了 100 个小球，显然他就知道所有人都来过房间了。问题的关键就是：为什么最终总会有一个人能集齐所有的小球？
其实，协议中的很多复杂的细节都是为了保证下面这个引理成立：每一个人离开房间之后，房间里都只可能有两种情况：
A. 跷跷板两侧的人一样多
B. 高的那边多一个人
这是因为，如果有囚犯第一次进入房间，他将坐上低的那一侧，并把那一侧扳高，于是原本是情况 A 现在就会变成情况 B ，而情况 B 则会变成情况 A ；另外，如果有囚犯下了跷跷板，高的那一侧将少一人，同时该侧将被扳低，同样有情况 A 将变情况 B ，情况 B 将变情况 A 。
现在，让我们假设所有人都进过房间了，并且有 k 个人正在跷跷板上（其余的人都已经离开跷跷板了）。由于跷跷板两侧最多差一人，因此当 k 大于 1 时，跷跷板两侧都是有人的。而由于每个人都进过房间了，因此不会有新的人坐上跷跷板了。此时，位于高处的人将不断拿出自己的球，并被位于低处的人取走。直到某个时刻高处有人拿不出小球了，他将走下跷跷板，此时跷跷板的状态才会发生变化，跷跷板上的总人数将变成 k-1 。最后跷跷板上只剩一个人时，显然他就拥有了所有人的小球，此时他就知道所有人都来过了。
容易想到，如果初始时房间的状态不定，人手两个球的改进方法同样能解决问题。当然，对问题的探索是永无止境的，我们相信囚犯与灯泡的问题还会有更多漂亮的变种和扩展，不断启发着人们的思维。即使这些问题没有任何使用价值，思考过程本身也是有益而有趣的。让我们感谢最初设计这个智力趣题的无名氏，他给我们带来了无尽的思维乐趣。