100囚徒难题

noski

100囚徒难题

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
更新：
201楼  oboe 指出18楼答案概率上的一些细节问题。
206 209楼  liulijie 将答案做了优化，前一百天使用不一样的规则，使最后所用的天数减少。
另外 210楼 liulijie 指出，在1000天后，也就是三年左右的时间，100个人都放过风的概率大于95%，囚徒们可以赌一下。

另外，大家如果不是讨论问题，不要回复2楼的贴子了，2楼的不是正确答案。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

[ 本帖最后由 noski 于 2009-1-18 01:20 编辑 ]

noski

嗯  似乎这些囚徒是活不到出狱那一天了

noski

其它99个囚徒没必要知道第一天放风的到底是谁，只要第一个放风的知道自己的使命就行了。

noski

这个赌博的想法很赞！三年都放过风的概率相当大。。
PS：国王奸笑道：嘿嘿，100号签就在我手里，他没放过风...玩笑