魔方吧·中文魔方俱乐部
标题: 100囚徒难题 [打印本页]
作者: noski 时间: 2005-3-12 17:25:50 标题: 100囚徒难题
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 编辑 ]
作者: xinru 时间: 2005-3-12 18:25:02
太简单！
囚徒们足可以利用20分钟时间把“灯”的确切位置公布给大家，所有囚徒就可以全部大赦了！
________________________________________________________________
注： 去除此贴的“回复”！
ggglgq
[ 本帖最后由 ggglgq 于 2009-1-18 12:53 编辑 ]
作者: shaolong 时间: 2005-3-16 09:11:49
it is so easy, turn on/off the light
作者: shaolong 时间: 2005-3-16 09:16:44
the sound
作者: simpley 时间: 2005-3-17 13:42:36
vb
作者: yy94193542 时间: 2005-3-26 20:37:53
顶下
作者: lok 时间: 2005-3-27 12:20:32
顶～～～～～～～～～
作者: ljjcom 时间: 2005-3-30 21:49:09
ok
作者: yoo 时间: 2005-4-1 20:48:01
good
作者: regedit 时间: 2005-4-3 17:02:20
不知道，怎么回事？
作者: AHWHITE 时间: 2005-4-21 18:46:43
实在好奇，看看答案
作者: AHWHITE 时间: 2005-4-21 18:48:07
…………被骗了，自己想。
作者: fbdfbd8055 时间: 2005-4-23 18:17:27
按照概率来算,不好说~
作者: houshen120 时间: 2005-5-6 16:18:56
[em06][em06][em06]
作者: 管窥子 时间: 2005-5-8 09:17:55
让我看看。[em01]
作者: cage 时间: 2005-5-29 14:35:34
幸亏不是囚徒
要不死定了
作者: dyer 时间: 2005-6-2 10:26:01
a
作者: hw294 时间: 2005-6-2 20:18:56
提示: 作者被禁止或删除 内容自动屏蔽
作者: noski 时间: 2005-6-3 08:48:46
嗯 似乎这些囚徒是活不到出狱那一天了
作者: 关门打狗 时间: 2005-6-3 09:40:56
连楼主也如是说？[em01]
作者: bennielf2 时间: 2005-6-25 15:13:02
看
作者: tswcbyy 时间: 2005-7-11 14:37:42
asdfsdf
作者: wave 时间: 2005-7-23 14:40:18
i want answer
作者: 霍亚 时间: 2005-7-31 23:54:31
九连环
作者: gdkool 时间: 2005-8-1 20:20:51
真的吗
作者: dj8008 时间: 2005-8-7 16:47:29
提示: 作者被禁止或删除 内容自动屏蔽
作者: 中山狼 时间: 2005-8-18 20:14:33
似乎
作者: xinru 时间: 2005-8-23 12:05:19
早看出来啦，中山狼是魔界的高手啦[em17][em17][em17]
作者: Cielo 时间: 2005-8-24 15:03:35
哦
作者: funcc 时间: 2005-10-24 16:50:37
提示: 作者被禁止或删除 内容自动屏蔽
作者: wz1a 时间: 2005-11-5 06:54:16
提示: 作者被禁止或删除 内容自动屏蔽
作者: ansel 时间: 2005-12-20 12:35:46
好可怜的囚犯~
作者: pumpitup 时间: 2006-1-22 01:02:16
不清楚,有办法么?
作者: pumpitup 时间: 2006-1-22 01:03:31
看懂了谢谢
作者: shift17 时间: 2006-2-27 17:31:26
……
作者: aw25 时间: 2006-11-14 19:42:41
ddddd
作者: panlm 时间: 2006-12-13 16:41:30
第三方
作者: lajiao 时间: 2006-12-24 18:57:29
天啊 当个囚徒都废脑子啊
作者: man690513 时间: 2006-12-27 15:08:40
dddd
作者: baotime 时间: 2007-1-3 21:16:40
不停得开关
作者: bawanglb 时间: 2007-1-22 11:07:40
以前在读者文摘上看见过，但是又忘了，这个题目是很好的一个题目，就是利用那个灯来达到目的。
作者: whitetiger 时间: 2007-1-25 13:56:45
楼主有与18楼不同的答案吗？
作者: whitetiger 时间: 2007-1-25 13:57:07
楼主的答案真是别出心裁！
[此贴子已经被作者于2007-1-25 14:02:32编辑过]
作者: whitetiger 时间: 2007-1-25 13:57:34
开始误以为是另一个“100囚犯”问题，这么晚才看到。
[此贴子已经被作者于2007-1-25 14:03:31编辑过]
作者: daiyaotim 时间: 2007-1-27 20:24:34 标题: 有更好的答案？
？
作者: 380240947 时间: 2007-2-10 15:16:40
顶
作者: 88558855 时间: 2007-2-16 11:17:41
dfgjdkdykruyird
作者: mfblackdog 时间: 2007-2-24 00:34:42
是不是很简单？
作者: 吗哈 时间: 2007-4-2 10:49:53
十八楼?
作者: icemanzxq 时间: 2007-4-12 14:57:42
看一下
作者: 奇遇 时间: 2007-5-1 19:13:43
瞧瞧
作者: 阿牛++ 时间: 2007-5-10 17:54:35
不懂
作者: ctkevin 时间: 2007-5-22 17:22:09
没想出来,只好参考答案了....
作者: gt750228 时间: 2007-5-26 17:33:28
[em01]
作者: zami 时间: 2007-5-28 17:55:01
hutu [em01]
作者: danfeg_du 时间: 2007-6-6 14:28:58
好
作者: Arcan 时间: 2007-6-15 00:07:55
对hw294的答案再优化一下：
第一天出来的人将灯打开。
第二天出来的人如果是第一天出来的人，那么将灯关闭，否则不对灯进行操作。
第三天出来的人负责计数，如果看到灯开着，那么证明至少2个人已经放过风了，如果看到灯闭着，那么证明已经有1个人放过风了。
后面的步骤跟18楼描述一致，这样第三天的人就可以减少一次或两次的计数，总时间上可以节省100~200天，呵呵，不过相对30年来说影响还是不大。
作者: moneyyyyy 时间: 2007-6-26 13:40:06
看看什么答案
作者: piaoling886 时间: 2007-7-7 16:21:15
顶顶顶顶顶顶顶
作者: zhjiemm 时间: 2007-7-8 12:23:19
只有一个灯，还有其它办法不？
作者: zhjiemm 时间: 2007-7-8 12:26:12
57楼的算法有问题哦。
作者: LIDIN123 时间: 2007-7-26 00:33:31
顶～～～
作者: pumpitup 时间: 2007-7-27 15:15:35
嘿嘿,57楼的俺没看懂
我觉得也只能99人个负责开灯,一个人负责关灯这个方法.
附加一下,如果不知灯的初始状态的话,第一天出来的人负责把灯关掉就可以了.
建议lz整理整理一下可以锁贴了.一楼题目,二楼答案.有什么问题可以开新贴.这样太乱了.
作者: ghos 时间: 2007-7-31 18:47:27
想不到
作者: d1357 时间: 2007-8-16 19:59:26
回复[em02]
作者: libiamo 时间: 2007-8-17 04:47:28
d
作者: 天眼偶开 时间: 2007-8-30 15:41:49
顶啊
作者: 隔夜 时间: 2007-8-31 21:23:59
我想了15分钟 就想出来了
定一个人做记录者(可以选第一个) 记录者专门负责开或关的其中一种 如果他负责开灯那么其余人都不能开灯 只能关灯 并且除记录者外的其他人每人只能关灯一次(这是关键前边没提到)
如果记录者连续的两次防风之间的时间内 有个第一次防风出来的人 那人就会关灯告诉记录者又多了一个"已经放风的人" 直到记录数到达100
题外的思考:上述方法的确能保证所有人的有放风,100%的保证 时间期望估算一下要30年(一万天),如果他们等不及出狱的话,可以考虑冒险估算路线.成功机会99%也未尝不可一试,大家可以估算一下,某个囚犯每天有99%的机会放风失败,我按一下计算器,连续200天放风失败机会是0.99的200次方=0.13397967 连续300天放风失败的机会是0.0494089 连续500天放风失败的机会是0.006570 连续800天放风失败的机会是0.000322222连续1000天放风失败的机会是0.000043171247
大家发现了没?还用等30年吗?
囚犯的正确做法会是什么?如果我是其中一名囚犯,根本不去管那盏破灯,老老实实呆3年(1000天),然后报告,我受够了,我确定每个人都已经放风了(这时囚徒被处死的机会低于两万分之一,这个概率可理解为一次单独试验中不可能发生事件,再说2万分之一这概率低于在监狱的死亡率吧)
这样,无期徒刑变3年徒刑,才是真正的大赦,这才是聪明的囚徒和国王
综上,这题的正解是囚犯们应该什么都不做,等到一个适当的时机(3-5年左右),然后就可以确定了
作者: 隔夜 时间: 2007-8-31 21:47:03
我是68楼
我补充说明一下 什么是"不可能发生事件" 不可能发生事件:"一次"独立试验中发生可能性极小(小于千分之一,没有绝对界限)的事件,我们可以看成是不可能发生的,"一次"是重点
不可能发生事件并不是概率为零.上题中,我把万份之一的机会当成了绝对的不可能发生
也许有人会问,概率上的万份之一说大不大,说小不小,怎么会是不可能的呢?百万份之一的彩票也会有人中
的确,百万份之一的彩票也会有人中,可彩票不是只卖一张的,可能是上亿张(彩池累积好几次),大家买彩票,我不中,你可以中,"有人中"发生的机会就大了,如果要指定一个人要他中奖,我可以说他一辈子也中不了
不可能发生,并不是绝对不能发生,至少数学家们敢肯定想要"一次"试验中想要出现是不可能的.
作者: jasonwater 时间: 2007-9-8 02:05:31
看看答案
作者: TOYOTA 时间: 2007-9-8 21:48:32
看看拉
作者: pixiu77 时间: 2007-9-12 11:41:58
提示: 作者被禁止或删除 内容自动屏蔽
作者: fxnew 时间: 2007-10-22 20:02:35
看看
作者: 钟七珍 时间: 2007-10-23 16:29:21
怎么回事？
作者: tangbate 时间: 2007-10-27 23:38:45
不会
作者: pilyfe 时间: 2007-11-2 11:19:28
补充68楼
事先规定：第一年开灯；第二年关灯；第三年开灯；第四年关灯......
第一年，出来的人都保证灯是开的。第二年，第一个出来放风的人如果是第一次出来放风，则开灯；否则，关灯。后面出来的人如果是第一次出来放风，则开灯，否则，不要操作。第三年，第一个出来放风的人如果是第一次出来放风，则关灯；否则，开灯。后面出来的人如果是第一次出来放风，则关灯，否则，不要操作。第四年，第一个出来放风的人如果是第一次出来放风，则开灯；否则，关灯。后面出来的人如果是第一次出来放风，则开灯，否则，不要操作......
从第四年年开始，某个囚徒发现前6次出来放风灯的状态都与事先规定相吻合，那么，就可以站出来说，大家已经全部放过风了。否则，就再等一年。
[此贴子已经被作者于2007-11-2 11:31:36编辑过]
作者: simpley 时间: 2007-11-4 00:13:24
以下是引用隔夜在2007-8-31 21:23:59的发言：我想了15分钟 就想出来了
定一个人做记录者(可以选第一个) 记录者专门负责开或关的其中一种 如果他负责开灯那么其余人都不能开灯 只能关灯 并且除记录者外的其他人每人只能关灯一次(这是关键前边没提到)
如果记录者连续的两次防风之间的时间内 有个第一次防风出来的人 那人就会关灯告诉记录者又多了一个"已经放风的人" 直到记录数到达100
题外的思考:上述方法的确能保证所有人的有放风,100%的保证 时间期望估算一下要30年(一万天),如果他们等不及出狱的话,可以考虑冒险估算路线.成功机会99%也未尝不可一试,大家可以估算一下,某个囚犯每天有99%的机会放风失败,我按一下计算器,连续200天放风失败机会是0.99的200次方=0.13397967 连续300天放风失败的机会是0.0494089 连续500天放风失败的机会是0.006570 连续800天放风失败的机会是0.000322222连续1000天放风失败的机会是0.000043171247
大家发现了没?还用等30年吗?
囚犯的正确做法会是什么?如果我是其中一名囚犯,根本不去管那盏破灯,老老实实呆3年(1000天),然后报告,我受够了,我确定每个人都已经放风了(这时囚徒被处死的机会低于两万分之一,这个概率可理解为一次单独试验中不可能发生事件,再说2万分之一这概率低于在监狱的死亡率吧)
这样,无期徒刑变3年徒刑,才是真正的大赦,这才是聪明的囚徒和国王
综上,这题的正解是囚犯们应该什么都不做,等到一个适当的时机(3-5年左右),然后就可以确定了
1000天内失败的机会是0.0043171247，0.000043171247仅是对一个人而言。
作者: cj503 时间: 2007-11-11 18:45:58
提示: 作者被禁止或删除 内容自动屏蔽
作者: 奇遇 时间: 2007-11-17 12:57:07
瞧瞧看怎么个放风法
作者: shendy 时间: 2007-11-26 16:06:10
-_-!简单吗????????????/
作者: 迷路的麋鹿 时间: 2007-11-27 19:03:33
原帖由 <I>hw294</I> 于 2005-6-2 20:18 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=8532&ptid=699" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> <FONT size=5>当A第99次发现他打开的灯被关闭后，则可以确认所有人都放过风了。
<P><FONT size=5>A有大约一半次数的放风会看到灯是开着的，第99次发现他打开的灯被关闭，他大致上已放风200次，所以应该要大约经过20000天，约55年。</FONT></P>
作者: danfeng8385 时间: 2007-12-14 14:30:30
真的不好想
作者: 0萧枫0 时间: 2007-12-14 23:11:57
提示: 作者被禁止或删除 内容自动屏蔽
作者: Redeemer1001 时间: 2007-12-14 23:40:42
不想想了，看看高手的答案～～
作者: shurarai 时间: 2007-12-16 23:27:01
很好奇，顶一下，看看怎么回事
作者: bfans2004 时间: 2007-12-17 21:05:22
提示: 作者被禁止或删除 内容自动屏蔽
作者: 牙膏 时间: 2007-12-17 21:52:20
。。。。。。。。。。。。。。
作者: guonanwawa 时间: 2007-12-21 11:26:13
还是没想到更好的方法
作者: hubohui 时间: 2007-12-21 18:33:51
看下啦~想知道答案啦
作者: w-inds. 时间: 2007-12-23 17:06:48
来看下答案.........
作者: xiaohua594 时间: 2007-12-27 20:47:13
18楼的看了。看看2楼的再。
作者: wangpeng0636 时间: 2008-1-4 14:02:36
kanyixia hehe
作者: juliette 时间: 2008-1-15 19:56:10
看看
作者: shadowliao 时间: 2008-1-19 15:07:18
ddddddddddddddddddddd
作者: 怪兽 时间: 2008-1-19 21:04:56
不错哦，
作者: 宇枫 幽蓝 时间: 2008-1-22 15:04:53
顶上去，大家一起看下，喊冤啊~~~
作者: weet 时间: 2008-1-28 14:35:15
不知道。。。看答案
作者: 熙.~(煕 时间: 2008-1-31 00:38:46 标题: 顶～～～～～～～～～
顶～～～～～～～～～
作者: lingb01 时间: 2008-1-31 00:44:58
好问题 有待于
研究
作者: 立 时间: 2008-1-31 01:05:01
好惨啊.................................
| 欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/) |
Powered by Discuz! X2 |