名侦探柯南事务所

标题: 一道囚犯的题目 [打印本页]

作者: 小赖皮 时间: 2004-4-7 20:22
标题: 一道囚犯的题目
一个监狱里有奇数N个特聪明的犯人，每人都单独关在自己的牢房里，无法和其他囚犯做任何通讯。每天晚上囚犯可以聚在一起自由讨论一次。有天晚上有个犯人知道了这么个秘密消息：国王决定集体大赦囚犯，但是要考这些囚犯一个题目：在次日早晨，会有人来把每间牢房门的正面刷上或黑或白的颜色，颜色的选择是同等概率随机的（比如用抛硬币的方法决定门上该刷黑还是白色），犯人都不可能知道自己门上被刷了什么颜色。然后犯人会依次被叫到典狱长办公室里。走出牢房时，犯人有机会看见所有其他人门上的颜色，但是因为他自己的牢门是开着的，所以门正面靠着墙，他还是看不见上面的颜色。在办公室里典狱长向犯人通知这个大赦的决定，并且询问犯人对自己牢门上的颜色是黑是白的猜测。然后犯人被带回牢房，关好门后，下一个犯人再被叫出询问（在典狱长办公室里犯人是看不到前面其他犯人的回答的）。如此直到所有人都被叫出来一次。现在典狱长统计一下所有犯人的猜测，如果猜对自己门上颜色的犯人数过半，那么他就释放所有犯人，如果不过半，每个犯人都只好把牢继续坐下去。因为N是奇数，所以不会出现恰好一半犯人猜对的可能。现在犯人提前知道了这个消息。有人说，因为他们不能互相通讯，所以看见了其他人的门上颜色，对知道自己门上的颜色毫无用处，即使其他人门上都是黑色，自己门上颜色是白是黑还是可能性各半（因为每个门的颜色都是单独确定的）。所以无论怎么猜其实就是50%可能性
猜对，所以提前知道了这个消息也是白搭。你说这个推理对不对？为什么？如果你认为这个推理不对，那么犯人们就有机会在一起讨论制定一个策略，使得被释放的可能大于50%。那么如何制定这个策略，使得被释放的可能性尽量大？

作者: 小小孩 时间: 2004-4-8 12:42
标题: 回复：
每一個犯人都很難在牢獄中打眼色？？？

作者: 狂虎 时间: 2004-4-8 12:43
标题: 回复：
可以每个人都说是同一种色的

作者: 小小孩 时间: 2004-4-8 12:49
标题: 回复：
在出牢獄時，看到別人牢獄的顏色，便用暗號大聲說出。而在別的牢獄中的人則大聲對他喊出暗號～～

作者: HANNIN 时间: 2004-4-8 12:55
标题: 回复：
每个囚犯答对自己门上颜色的几率应该是四分之一。即使他们可以看到别的囚犯门上的颜色，但对
他自己是否可以猜对是没有影响的。也就是说每个囚犯的猜测几率的分布是独立的。
这样可知，无论是多少个囚犯，猜对的几率都是在四分之一左右，而几乎不可能有超过二分之一的机会。不知道这样理解对不对～

作者: 狂虎 时间: 2004-4-8 13:29
标题: 回复：
楼上的，为什么？
只有两种选择而已

作者: HANNIN 时间: 2004-4-8 13:40
标题: 回复：
比方说：一个囚犯他的门被刷上任何一种颜色的几率是二分之一，而他能够准确猜到两种颜色之中的一种的话，几率就是四分之一咯。根据概率统计应该是这样的。

作者: 狂虎 时间: 2004-4-8 13:46
标题: 回复：
那么换一种说法就是：猜对和猜错
这两种各占５０％的

作者: 莫里亚蒂 时间: 2004-4-8 14:02
标题: 回复：
如果在犯人出门时能说一句话就行，反之不行．
每个犯人出门时只须数一下有多少黑色和白色，然后说出数字就可以了．另一个犯人出来再数一次如果相同，则看第３个．．．．．．这样每个犯人只须把前面的与自己的做个比较就能知道是黑是白．
由于原几率是５０％，Ｎ个奇数犯人的几率是大于５０％

作者: 死者 时间: 2004-4-8 14:33
标题: 回复：
机率最大的是，全部认定一种颜色。

作者: stoneslot 时间: 2004-4-8 15:50
标题: 回复：

最初由 HANNIN 发布
比方说：一个囚犯他的门被刷上任何一种颜色的几率是二分之一，而他能够准确猜到两种颜色之中的一种的话，几率就是四分之一咯。根据概率统计应该是这样的。

0.5*0.5+0.5*0.5=0.5 乘法原则和加法原则懂吗？

怎么会是1/4

我ft

作者: popcorn 时间: 2004-4-8 16:23
标题: 回复：

最初由死者发布
机率最大的是，全部认定一种颜色。

同意
不过，觉得认定哪一种颜色是和每个犯人所看到的其他门的颜色有关。
怎么说呢，犯人总数N为奇数，他看到的应该是偶数个门。根据50%的概率，他应该选择门数较少的一方。（1）
如果他看到黑白数量相等就弃权。因为不可能每个人都遇到这种情况，根据概率，该有50%以上的人遇到1情况。
那就有有机会获释。
大概是这个意思，说不好，概率刚及格。%&013

作者: LIYI 时间: 2004-4-8 20:43
提示: 作者被禁止或删除内容自动屏蔽

作者: Agasa 时间: 2004-4-8 23:42
标题: 回复：
大概算了一下，基本同意13楼兄弟的意见。。既然他先说出来，偶也要有些创新，就讲一下理论算法吧。。

设较多颜色的门的个数为a，较少的为b；刷上较多颜色的门的百分比为P＝a/N，对应的，刷上较少颜色的门的百分比为1－P；猜自己门的颜色是较少颜色的囚犯占总囚犯数的百分比是X，对应的，猜是较多颜色的囚犯的百分比是1－X。。

主要有两种情况：
（1）当a－b>＝2时，任何囚犯都可以数出其他门的颜色哪个多哪个少(理由不难吧)。。
这样最后，猜对了门色的囚犯占所有囚犯的百分比Y＝猜是较多颜色且猜对了的囚犯的百分比＋猜是较少颜色且猜对了的囚犯的百分比＝P(1－X)＋(1－P)X＝P－(2P－1)*X
最后式子中，因为P > 50%,故2P－1 > 0，因此猜对的囚犯的百分比有个最大值——当X＝0，也就是所有囚犯都猜是他看到的较多的颜色时，为P，肯定大于50％，肯定被释放。。前提是要统一，要是有哪怕一个猜较少的颜色，就有少于50％的风险，情愿保守一点。。

（2）当a－b＝1时，就有13楼没有提到的一种特殊的情况发生——有一部分囚犯看到其他的门上黑白两色的数量相同，都是a－1＝b个。。
这种情况对囚犯是相当倒霉的，就要赌运气了，也是全部猜一种，只要猜对了，整体百分比将大于50％；赌输了就等着留在狱中被其他的囚犯揍扁吧。。

作者: FF29 时间: 2004-4-9 06:15
标题: 回复：
很简单，答案和上两楼一样，每个囚犯说出自己数到的比较多的那种颜色的门。

用概率分析，假设一共只有3个囚犯（最简单的例子），那么以这种方法可以获得赦免的机会是13/16。
详解：
1.三个门同色的机会为(0.5*0.5*0.5)*2=0.25，这是3人说出的颜色是相同的，因为每个人都看见两扇相同颜色的门，所以赦免机会100%。这样先得到最终答案的一部分：100%*0.25=25%
2.另一部分，三个门不同色的机会为1-0.25=0.75，但只能是2黑1白或2白1黑，以2黑1白举例（2白1黑完全相同）：白门囚犯看到2个黑门，一定说黑色，所以关键在另两人的答案。另两人看见的都是1黑1白，所以全靠猜测，但只有两人全猜白色，才失去赦免机会。全猜白色的几率是25%，所以2黑1白石成功赦免的机会是0.75*(1-25%)=9/16。
3.然后将以上两步的机会相加，即25%+9/16=13/16，即最终成功赦免几率。

五个囚犯的情况就复杂得多，不详细说，答案是61/64。
有兴趣的朋友可以算一下，或者算算更多囚犯的情况，反正囚犯越多，赦免机会越大。

欢迎光临名侦探柯南事务所 (https://bbs.aptx.cn/)