说有 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时，这样的协议明显存在！
占个sf先 :p
板凳…
m67牛 总是喜欢夜间发帖
这题..好熟..
发现自己又迟了
我正在想怎么给这类问题建立一个通用的模型。
这个问题来源绝对早于2001年，我在上个世纪就做个这个题目了。
0：12两帖连发……
0：12两帖连发……？
如果灯泡的初始状态并不确定，那就麻烦了：统计者收集了 100 个小球并不足以说明所有人都来过房间，而他有可能永远也等不到第 101 个小球。
哪位大牛解释一下这句话
简单的说就是统计者不知道该在收集了100个小球还是101个小球的时候断定所有人都进过这个房间.如果第100个的时候断定,因为一开始的房间有一个小球,那么有可能还有1个人没有进入房间过.如果准备等待收集到第101个的时候断定,那么如果一开始房间灯熄灭的话,统计者只可能收集到100个球,第101个球是永远无法出现的.
简单的说就是统计者不知道该在收集了100个小球还是101个小球的时候断定所有人都进过这个房间.如果第100个的时候断定,因为一开始的房间有一个小球,那么有可能还有1个人没有进入房间过.如果准备等待收集到第101个的时候断定,那么如果一开始房间灯熄灭的话,统计者只可能收集到100个球,第101个球是永远无法出现的.
看了半天，有点绕，不过觉得和悖论的分析有很类似的地方。如
http://www.chinaai.org/ai/others/paradox.html中的一句话：
“这句话是错的”。分析思路和上面的一样。
什么时候统计者收集到了200个小球（包括自己的两个），他就知道所有人都来过了，因为如果还有人没进房间，他最多只能拿到 198 + 1 个小球。注意，这 200 个小球可能就是囚犯手中的 200 个小球，也有可能是囚犯手中的 199 个小球加上初始时房间里的小球。体会一下这个协议如何巧妙地解决了房间初始状态不确定的难题，真是越想越有味道。
这个协议的巧妙之处就在于对：囚犯进入房间次数构造了一个范围区间。只需要囚犯至少进入一次房间即可，而初始状态的不确定性就包含在了这个允许的范围区间内。所以最后只需要搜集到200个小球就可以判断所有囚犯都到过房间里面。
不是只要选出一个人专门负责关灯。。而别人只在灯不亮时开灯（开过灯的就不要开了）就可以了么，反正是无穷次。最后负责关灯的那个人计满数就OK了。。干嘛这么饶呢
很不错咯！蛮有头脑的！
这个题目应该比2001年更早就有了。
我有一个答案。但不知道是否是最快出狱的方法：
众人约定：1号每到房间来一次，如果是灯是关着的，不管，如果是开着的，关之。其他人（1-99号）来房间的时候，如果某人是第一次来，并且如果灯是关着的，开之。否则不管。当1号关了99次灯之后，可以确认每个人都来过房间了。
回18楼，你的方法和文中的方法是一样的，只是开灯和关灯调换过来而已
很不错咯！蛮有头脑的！
这个和100 个囚犯问题不一样啊，每个囚犯都可能进去无数次，每次进去他都可以拉亮灯或拉灭灯，计数的囚犯只能通过等亮或灯灭获知进房间多少次，他怎么可能进去了哪些人呢，同1个人进去100次呢
加强版问题的逗比答案，老样子一个人数，数到100把等打破，剩下人看见灯破的就知道都来过了。巧计勿喷，剩下是否还有别的方法还在想
但是，如果有个人，没有这么做，然后，自己计数，最后，他的答案和别人不一样，但是自己走了！岂不美滋滋
关于最后的问题我有个想法（虽然按照这个方法期望时间十分之长）
收集完所有小球之后，这个人只要不断的放球收球，足够长的时间之后，其他所有人都可以观察到小球消失-出现超过200次，那么可以完全确定这是收集完给出的信号。
现在说这个可能有点晚了，但是这方法不行。有可能统计者开始放出完成信号之后，每次都连续两次进入房间。这样就没有任何人能看到它发出的信号。