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 编辑 ]

kilominx

一百个囚徒联合起来把国王杀了就行（

liquidsheet

2023年前来考古
一开始看到这个问题，很长时间都觉得这道题无解，甚至试图证明这个题一个必要条件无解，但是竟然有人逐渐优化答案至原来的一倍以上，大佬原来早就在研究了

鸦雀无声

啥意思不懂

大魔王檀石槐

原来这就是随机啊. 我可以留一个房间一直不去让他放风,嘿嘿,我邪恶地笑!

超魔

都是高手啊，我怎么就想不明白呢!

[ 本帖最后由 超魔 于 2009-2-28 14:52 编辑 ]

棉花糖three

顶！~~~~~~~~~~~~~~~~~~~~~~~~~

lulijie

金眼睛看来是真的很忙，题目的本意当然不是让赌徒赌博。
若考虑到赌博方案的话，最早68楼就提出来了。

金眼睛

原帖由 lulijie 于 2009-2-14 22:14 发表
从223#后面的计算公式上可以看出，楼主应该是考虑到了全部放过风的概率，可是计算500天的概率，不知为什么算错了，以致得出了错误结论。
500天全部放过风的精确概率=1-C(100,1)*0.99^500+C(100,2)*0.98^500-C(100,3 ...

lulijie您好，请注意“平均500多天，囚犯们基本上就都放过风。”中的“平均”及“都”，平均当然是50%啦，呵呵!我说话有时候不是很标准，我本身不是学数学的，请关注这种想法本身。

我并不是说大家提出的方案不好，只是提出一种观点让大家注意，就是假设一种方案平均需要N天能够成功，其使囚犯老死狱中的概率为a，而犯人什么都不做到第N天提出请求被杀头的概率为b，如果a大于b，则说明这种方案并不很好。

如果这样的方案不存在，换个思路可以认为国王给犯人们设下了思维陷阱，没有灯大家可能还会赌一把，有了灯反而使大家陷入思维定势、犹豫不决，这个只是我的一点想法，如果方案存在另当别论。

工作比较忙，偶尔才能来一次，可能都有人能猜出我的工作，呵呵！希望lulijie等魔友积极活跃论坛，我也是通过学习魔方，慢慢开始痴迷于这个版块的，希望大家能在G老师的领导下将它越办越好。

lulijie

从223#后面的计算公式上可以看出，楼主应该是考虑到了全部放过风的概率，可是计算500天的概率，不知为什么算错了，以致得出了错误结论。
500天全部放过风的精确概率=1-C(100,1)*0.99^500+C(100,2)*0.98^500-C(100,3)*0.97^500+C(100,4)*0.96^500-C(100,5)*0.95^500+……=1-0.65705+0.20307-0.03932+0.00536-0.00005+……≈51.2%
与电脑模拟算出的概率相近。