来一道有名的谜题目：100个囚犯和一盏灯

fczwy

真名网乃藏龙卧虎之地，小弟最近想一道题目，想得有点头大，想找个人切磋一下：

有100个无期囚徒，被关在100个独立的小房间，互相无法通信。
每天会有一个囚徒被完全随机地抽出来放风。
放风的地方有一盏灯，囚徒可以打开或者关上，除囚徒外，没有别人会去动这个灯。每个人除非出来防风，是看不到这个灯的。
一天，全体囚徒大会，国王大赦，给大家一个机会：如果某一天，某个囚徒能够明确表示，所有的囚徒都已经被放过风了，而且的确如此，那么所有囚徒释放；如果仍有囚徒未被放过风，那么所有的囚徒一起处死！
囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？

 

 

韧苇

方法如下：

首先，囚徒们确定第一天出去的那个人（无论为谁）负责开灯，我们特定其为亮亮；
其次，其余99个人只负责关灯，要求是：每个人第一次出去的时候见到开的灯就关掉，下次出去，不管灯开与否都不再动开关；如果第一次出去发现灯是关着的，则不得动开关，等到下一次出去见到灯是亮着的时候再关灯（如果第二次出去还是关着的，仍然不得开灯，依此类推……）；
再者，亮亮从第一天开始记开灯次数，如果他出去后，见到灯是关的就打开，同时在他记的数上加一，如果灯是亮的，就保持原状。直到亮亮记的开灯数达到99次（不包括他的第一天的第一次开灯），而且他再出去时灯是关的，亮亮就可以宣布所有的人都出去过了。

问题在于：这样的概率实在太低，因为每一次被放出去放风的囚犯都是随机抽取的，亮亮每次被抽中的概率很低（只有百分之一），而只有当他被随机抽中一百次之后才能确定所有的人都已经被放风过了。这得需要多长的时间啊？！有可能已经经过几十年了。所以国王一点也不仁慈啊！

周泽雄

这可能是讲概率的吧，我不懂概率学，但按韧苇妹子的办法，正常情况下大概需要三十年（100乘100=10000天），和无期徒刑差不多了。理论上最快的可能性，是一百天后大家依次轮到，然后在第101天大家一起出狱。这不可能。相对说来比较倒霉的一种情况该是多少呢？我们可以假设，大概到了一百天后，有70个人都出去放过风了，到了两百天后，有95个人去放过风了，最后5个一直没有摇到号的人，有没有希望在第三个一百天里被抽中呢？如果有可能，那么，设法找到最后一个出去的人。由于通风报信的手段只是两种：要么开灯，要么关灯。而这盏灯平时非关即灭，假如约定平时是关着的，当最后一个人（假定以三百天里从未放过风为标准）有把握确信自己是最后一个，他就可以开灯通知。除非有人发生异议（可用关灯来更改），否则，当这个人下回被轮到时发现灯仍然是开着的，他大概就可以宣布所有人都放过风了。否则，就改让那个有异议的人（漏网者）负责监督下一个轮回。关键是：让开灯与关灯的动作，掌握在最后两个人手上，别的无关紧要的人，不要有任何举动。按这种办法，大概两年后可以全体出狱。是否万无一失，就不知道了。比如说，偏偏有一个家伙两年来（即700多天）从未被抽中过，那就太倒霉了。

这肯定不是最好的办法。掺和掺和。

[此贴子已经被作者于2006-8-25 18:30:42编辑过]

猪头猪智慧

俺是一脑袋浆糊，整不明白。

李酒苗

瞎问问，可否摘下灯泡？

人约黄昏后

还是酒苗兄干脆，摘下灯泡算了！

李酒苗

以下是引用人约黄昏后在2006-8-25 21:42:00的发言：
还是酒苗兄干脆，摘下灯泡算了！

更干脆的是，约好了第三年的最后一天宣布出狱。平均每人可以放风十天，如果还轮不到放风，不如自杀，成全了别人。

金塔

如果允许的话，在墙上画线多简单，一百条线一百个人放风。

灯是什么？就是一个给出的条件，不用就完了。没有给出的条件才是解决问题的关键。

萧雪

其中99个人只能关一次灯~~~
另外一个人见到灯关就给打开~~由此来计算几个人关过灯~~
如此只要开了99次灯就可以出狱了~~~~~~~
方法：

1。确定第一天出去的那个人为证明的那个人，也是永远只负责开灯的那个人。
2。其余99个人是关灯的人，要求是：见到开的灯就关掉，而且，在这个过程中，他只能关灯一次，关了一次以后，下次出去，不管灯开与否都不能动开关。
3。被确定为证明的那个人从第一天开始记开灯次数，如果他出去后，见到灯是关的就打开，同时在他记的数上加一，如果灯还是亮的，就不动开关，这样，当他记的开灯数到99次，而且他出去时灯是关的，说明所有人都出去了。

萧雪

抄滴

fczwy

这题其实和概率关系不大，当然也非脑筋急转弯的类型（有人说：把灯泡打碎，分成100块，每人拿一块，拿完为止：），题目的意思很简单，就是只通过一盏灯的开、关两个状态，来找到一种方法确保100人都到过的那个房间。注意是确保，就是说您的方法必须保证100人都到过了，所以周泽雄兄的方法，呵呵，有点危险，搞不好100个人就都砍头了。

1. 方法一很简单，上面的贴子已经说到了，第一天出来的这个囚徒负责关灯，以后出来的囚徒：
1）当灯是关着的时候，如果他没有开过灯，那他可以打开灯，否则他不能开灯；
2）当灯是开着的时候，他不动灯。
3）第一个囚徒在他放风的时候，如果发现灯是开的，那么他就关闭灯。这时他就把放过风的囚徒数加一。
当第一个囚徒的计数达到99的时候(加上他自己是100)，他就可以宣布所有的囚徒都放过风啦。

2. 方法二可以省一点时间，因为是完全随机的抽取，所以前面被重复抽到的概率比较小，所以一开始不固定哪个是记数员，记数员定为第一次被重复抽到的那个人为记数员，
分两个阶段：
阶段一：前100天决定谁来计数。
1）第1-99天，初始灯关着，第一个两次放过风的人将成为计数者，并将灯关上。设其为第K天第2次放风，则他知道已经有k-1个人放过风，做为100天后计数的初始值。
2）第100天放风的人如果看见等关着，则宣布所有人都放过风；否则把灯关上
阶段二：100天后（按方法一计数）
1）如果计数者放风看见灯开着，则将放过风的人数加1，到100时宣布胜利
2）其他人如果以前没放过风，并且灯关着，则开灯，否则不动

3. 方法三（我到现在也没有想明白），

第三种方法提示如下:分为一个基本记数者和N个2级记数者,基本记数者的独立记数上限Cp和2级记数的独立计数上限Cs,时间由长度为S1和S2的两段交替组成.在S1阶段,计数者计数直到达到其独立计数上限,在S2阶段,达到计数上限的2级计数者将通过开灯方法告诉基本计数者直到基本计数者得到所有2级计数者完成任务并加上自己计数为100时宣布自由.

（我想不明白的地方就是：如果在S2阶段，有个2级计数者开了灯，但基本记数者还没有被抽到就又到S1阶段，那怎么办？？）

王代赟

看得脑袋里的糨糊都满得都溢出来了……

周泽雄

刚刚看到fczwy的批评。呵呵，俺是胡诌的，其实，俺最怵这种题目了。不过好在这只是纸上风险，否则，俺是万万不敢插嘴的。

但关于这个谜题，如果必需将囚犯的现实情况考虑在内的话，我会把任何一个必须计满100才有效的办法排除在外的，理由很简单：一百个囚犯在三年里（或一年里）死掉个把的概率，实在太高了。除非游戏条件里先假设这个条件不成立，否则，任何一个必须将100（这也是惟一确保的数字）作为万全之策的方案，都可能意味着无期徒刑。也许一年后你就永远数不到100了，两年后只能数到95了。

[此贴子已经被作者于2006-8-29 23:27:16编辑过]

fczwy

呵呵，我想这个算法问题的本质是：在共享通信信道且信道狭窄的情况下，如何更有效率的传播信息。应该说囚犯和灯都只是借以表达这个问题的道具。想像一下，当囚犯死了N多的脑细胞后想出了一个算法，结果发现灯坏了，那当真是哭笑不得......

xuhong

偶实在不知道这个灯泡要来做什么？？

100天，100个囚徒，没有规定谁先放风，管他呢，100天后，那个指定的囚徒跳出来说大家都放过风好了。

[em09][em09][em09]