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时,这样的协议明显存在!

25 条评论

  • tomsun11

    板凳…

  • hhtytommy

    m67牛 总是喜欢夜间发帖

  • D

    这题..好熟..

  • 欺天

    发现自己又迟了

  • 火星人

    我正在想怎么给这类问题建立一个通用的模型。

  • morrowind

    这个问题来源绝对早于2001年,我在上个世纪就做个这个题目了。

  • maa04

    0:12两帖连发……

  • maa04

    0:12两帖连发……?

  • wuzhengkai

    如果灯泡的初始状态并不确定,那就麻烦了:统计者收集了 100 个小球并不足以说明所有人都来过房间,而他有可能永远也等不到第 101 个小球。

    哪位大牛解释一下这句话

  • onlyxuyang

    简单的说就是统计者不知道该在收集了100个小球还是101个小球的时候断定所有人都进过这个房间.如果第100个的时候断定,因为一开始的房间有一个小球,那么有可能还有1个人没有进入房间过.如果准备等待收集到第101个的时候断定,那么如果一开始房间灯熄灭的话,统计者只可能收集到100个球,第101个球是永远无法出现的.

  • AirFly

    简单的说就是统计者不知道该在收集了100个小球还是101个小球的时候断定所有人都进过这个房间.如果第100个的时候断定,因为一开始的房间有一个小球,那么有可能还有1个人没有进入房间过.如果准备等待收集到第101个的时候断定,那么如果一开始房间灯熄灭的话,统计者只可能收集到100个球,第101个球是永远无法出现的.

    看了半天,有点绕,不过觉得和悖论的分析有很类似的地方。如
    http://www.chinaai.org/ai/others/paradox.html中的一句话:
    “这句话是错的”。分析思路和上面的一样。

  • AirFly

    什么时候统计者收集到了200个小球(包括自己的两个),他就知道所有人都来过了,因为如果还有人没进房间,他最多只能拿到 198 + 1 个小球。注意,这 200 个小球可能就是囚犯手中的 200 个小球,也有可能是囚犯手中的 199 个小球加上初始时房间里的小球。体会一下这个协议如何巧妙地解决了房间初始状态不确定的难题,真是越想越有味道。
    这个协议的巧妙之处就在于对:囚犯进入房间次数构造了一个范围区间。只需要囚犯至少进入一次房间即可,而初始状态的不确定性就包含在了这个允许的范围区间内。所以最后只需要搜集到200个小球就可以判断所有囚犯都到过房间里面。

  • whitefirer

    不是只要选出一个人专门负责关灯。。而别人只在灯不亮时开灯(开过灯的就不要开了)就可以了么,反正是无穷次。最后负责关灯的那个人计满数就OK了。。干嘛这么饶呢

  • orbea jersey

    很不错咯!蛮有头脑的!

  • hyperfree

    这个题目应该比2001年更早就有了。
    我有一个答案。但不知道是否是最快出狱的方法:
    众人约定:1号每到房间来一次,如果是灯是关着的,不管,如果是开着的,关之。其他人(1-99号)来房间的时候,如果某人是第一次来,并且如果灯是关着的,开之。否则不管。当1号关了99次灯之后,可以确认每个人都来过房间了。

  • 劣质数轴

    回18楼,你的方法和文中的方法是一样的,只是开灯和关灯调换过来而已

  • cervelo

    很不错咯!蛮有头脑的!

  • gj

    这个和100 个囚犯问题不一样啊,每个囚犯都可能进去无数次,每次进去他都可以拉亮灯或拉灭灯,计数的囚犯只能通过等亮或灯灭获知进房间多少次,他怎么可能进去了哪些人呢,同1个人进去100次呢

  • LH

    加强版问题的逗比答案,老样子一个人数,数到100把等打破,剩下人看见灯破的就知道都来过了。巧计勿喷,剩下是否还有别的方法还在想

  • 无音

    但是,如果有个人,没有这么做,然后,自己计数,最后,他的答案和别人不一样,但是自己走了!岂不美滋滋

  • lxblxclxd

    关于最后的问题我有个想法(虽然按照这个方法期望时间十分之长)
    收集完所有小球之后,这个人只要不断的放球收球,足够长的时间之后,其他所有人都可以观察到小球消失-出现超过200次,那么可以完全确定这是收集完给出的信号。

    • AccBalx

      现在说这个可能有点晚了,但是这方法不行。有可能统计者开始放出完成信号之后,每次都连续两次进入房间。这样就没有任何人能看到它发出的信号。

回复给 Arrow Rowe 取消回复

47  +    =  52