说有 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时，这样的协议明显存在！
声明：文章转自Matrix67博客，版权归原作者所有，转载仅供学习使用，不用于任何商业用途，如有侵权请联系删除，谢谢。
