100个囚犯和灯泡的那些事儿(下)

    即使灯泡的初始状态不定,当 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 。最后跷跷板上只剩一个人时,显然他就拥有了所有人的小球,此时他就知道所有人都来过了。

    容易想到,如果初始时房间的状态不定,人手两个球的改进方法同样能解决问题。当然,对问题的探索是永无止境的,我们相信囚犯与灯泡的问题还会有更多漂亮的变种和扩展,不断启发着人们的思维。即使这些问题没有任何使用价值,思考过程本身也是有益而有趣的。让我们感谢最初设计这个智力趣题的无名氏,他给我们带来了无尽的思维乐趣。

21 条评论

  • Eagle_Fantasy

    沙发~~这年头抢沙发不容易

  • 严酷的魔王

    这年头抢沙发真不容易……

  • lazyye

    抢沙发不容易啊……

  • ST.carly

    哈哈!
    尽力意会这些神奇的事。

  • vichare

    我觉得这个证明过程描述得不够清楚。
    这个证明首先要假设每个人不知道自己是第几个进来的(否则完全可以设计一个协议,使得所有人都知道所有人都进来过),然后假设每个人的策略都是确定性的。论证过程感觉也不是很严谨。

    另外,那个跷跷板协议为什么要把高低反过来说?很反直觉。跷跷板其实更像一个初始不平衡的天平,假设每个人重量一样,跷跷板开始的时候某一边有一个不到一个人重量的重物。个人感觉这样的表述清楚些。

  • vichare

    我个人认为n>2时,是存在一个带有随机性的策略使得能够以概率1在有限时间内有2个人断定所有人在房间里

  • anntgg

    时间不够,我很费劲可还是没看完,咱数学专业毕业后回头再看数学竟也是如此吃力,想来工作后没有了大学时候的专注了吧,留个记号
    顺便:博客很多链接都失效了,做个链接就应该保持互访的,不然做什么链接?改改吧

  • liushuoshu

    跷跷板策略里:
    每个囚犯第一次进入房间后,他都幻想自己坐到跷跷板低的那一边上,然后把自己这一侧扳高。
    以后每次回到这个房间时,自己所在的那一侧如果是高的话,他就在盒子里放一个小球

    也就是说如果他第二次来到这个房间,房间的状况跟他走的时候一样的话,他会把小球放到盒子里

    这个做法与之前问题的引理”因此,我们可以假设,当他进入房间时看见的状态和上次走的时候一样,他是不会去扳动开关的。”是矛盾的,说明之前的引理是有问题的.

  • 多级液下泵

    不错,顶,顶,顶,再顶

  • tdoal00

    9楼认真思考
    上次走时盒子里面有小球
    再进来如果真的和走时一样就放不进去了确实什么事也没做

  • orbea jersey

    想法很不错,值得考虑!

  • Arr

    “两个灯泡+所有人都必须遵循同一套策略”

    这个问题有一个更简单的解法:每个人第一次进入房间时如果A灯是灭的,就将其打开,并任命自己为统计者,收集别人的小球(B灯);如果A灯是开的,就按照非统计者的操作放小球(B灯)。这样第一个进入房间的人就是唯一的统计者,问题解决。

  • cervelo

    不错,顶,顶,顶,再顶

  • rmy

    大神解答一下为什么我的方法不对…:首先一个人收集球(和之前的一样)收集到200个球了以后他就知道所有人都来过了,然后他改变策略,每次来就改变状态,这时候如果其他的人看到状态改变超过200次了以后他就知道所有人来过了…

    • 18

      其他人未必能看到状态改变吧,可能一些人永远看到灯亮,另一些永远看到灭

  • rmy

    好像最后一个不是200次好像是400次…

  • Simon Zhou

    卧槽跷跷板的方法神了好吗?!我已经可以想象到小球在跷跷板上面沿着斜坡滚动的感觉了!其中高处有人下去了他就会改变跷跷板方向,然后小球批量反向滚动,另一侧又有一个人下去!不断重复!两侧不断有人下去!直到收敛到跷跷板上只有两个人,一个人全部把球滚给了最后一个人!

    不过博主的解释方法需要有一个补充:那就是,跷跷板初始低的哪个位置有0.5个人的负重!因为灯泡只有2种状态,所以跷跷板其实也只能有两种状态。
    这样就能保证两边人数一样多的时候,跷跷板总是往更重的地方下沉,而另一边人数更多的时候,就往另一边下沉。
    (也就是楼主的B状态:高的那边多一个人,其实意思是,全程只可能有一边多一个人,要不就是两边人数一样多,不可能出现第三种状态)

  • wonder721

    为什么这个题目会搞得这么复杂呢?是我太单纯了吗?
    我只要把100个人分成三部分。其中第一部分就是随机抽取的第一个人,他负责记下第一次灯的状况,这里假设是亮着的。剩下的99人,一部分人49负责开灯。另一部分人50负责关灯。首先,因为灯是开着的,然后,只有随机选到的是那个负责关灯的那一部分人。才会对灯的状态做出动作,依次类推,灯状态发生了变化,第一部分的那个人就要记一次。当负责开灯的人都开过灯了。负责关灯的人都关过灯了,最后那个第一部分的那个人也就相当于他记了一定次数(这里我不会算啦)就证明了哈哈哈吧。

发表评论

8  ×    =  48