魔方吧·中文魔方俱乐部

标题: geslon难题系列之一：囚徒脱困难题 [打印本页]

作者: geslon 时间: 2008-3-21 11:39:33 标题: geslon难题系列之一：囚徒脱困难题

有三个囚徒被关押在三个囚室，每个囚徒从门上的小孔口可以观察到其他二人的房门。某一天，监狱长告诉他们，三间囚室门外都将被随机的油漆成黑或者白两种颜色之一，油漆完毕后，他们三个人都必须对自己的房门颜色做一个猜测，如果三个人有至少两个人猜对了自己房门颜色，那么就把三个人都释放。
 
在开始油漆之前，允许他们三个人可以开个短会讨论一下，然后他们将被恢复到单独关押的状态。油漆之后，每个人可以看到别人房门的颜色，但是不再有机会通话或者发信号，只能独立投票。
 
试问：囚徒们是否有策略让自己被释放的概率达到最大，而不是1/2？
 
再问：如果是5个囚徒，必须达到3票，策略又是什么？释放的概率可以达到多大？

[ 本帖最后由 geslon 于 2008-3-21 11:41 编辑 ]

作者: Tain 时间: 2008-3-21 21:06:14

这会有策略吗?
论坛不应该限制发帖字数的

作者: geslon 时间: 2008-3-22 08:44:30

策略是有的。

这个题目之妙处也就在此，随便胡蒙，也是50%的概率。不可能知道答案的情况下，居然有策略可以超过50%的概率逃生，耐人寻味。

作者: Tain 时间: 2008-3-24 21:13:23

想不出来,楼主能公布答案吗?

作者: geslon 时间: 2008-3-24 23:58:24

可以公布答案，再等一天吧。

作者: Cielo 时间: 2008-3-25 13:25:36

3个人（甲乙丙）的情形： 可取策略：若其他两人的门都是黑色（或白色），那他就猜白色（或黑色）；若其他两人的门一黑一白，甲和乙猜白色，丙猜黑色。 这样总共8种情况中的5种他们会被释放，分别为黑白黑、黑白白、白黑黑、白黑白、白白黑。但不知道5/8是不是最优。 5个人的情形可能也差不多吧，32种情况感觉太多了，懒得想-_-| 

[ 本帖最后由 Cielo 于 2008-3-26 13:36 编辑 ]

作者: whitetiger 时间: 2008-3-25 15:37:39

我扔一块砖头。
 
可以用这样的策略：
如果看到另两扇门的颜色一样，那么猜测自己门的颜色也是这个。
如果看到另两扇门的颜色不一样，那么猜测自己门的颜色是黑的。
 
三扇门同色时（1/4），囚徒能获释；
三扇门两黑一白时（3/8），三人都猜黑色，囚徒也能获释；
三扇门两白一黑时（3/8），三人全猜错，囚徒不能获释。
 
获释的概率是5/8。
 
对于5个囚徒的情况，可以用类似的策略：取多，否则就指定颜色（黑）。
只有在三白两黑时全部猜错，其他囚徒都能获释。
囚徒获释的概率是11/16。

[ 本帖最后由 whitetiger 于 2008-3-25 15:43 编辑 ]

作者: Cielo 时间: 2008-3-25 18:48:38

原帖由 whitetiger 于 2008-3-25 15:37 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=102942&ptid=6972" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
我扔一块砖头。
 
可以用这样的策略：
如果看到另两扇门的颜色一样，那么猜测自己门的颜色也是这个。
如果看到另两扇门的颜色不一样，那么猜测自己门的颜色是黑的。
 
三扇门同色时（1/4），囚徒能获 ...

顶！策略比我的简单而且可以推广！

作者: geslon 时间: 2008-3-27 07:55:57

5/8 > 1/2，好！谢谢两位积极动脑！ 
我的策略如下：假设3人分别叫做ABC。当一个人看到两个黑门，他就猜自己白；看到两个白门就猜自己黑；看到一黑一白，就猜自己和左邻一个颜色。假设A的左邻是C，B的左邻是A，C的左邻是B。这样，当以下8种情况： 
 
A B C 猜测结果正确情况
黑黑黑白白白 XXX 
黑黑白白黑白 XOO 
黑白黑黑白白 OOX 
黑白白黑黑白 OXO 
白黑黑白白黑 OXO 
白黑白白黑黑 OOX 
白白黑黑白黑 XOO 
白白白黑黑黑 XXX 
 
这样，6/8 机会过关。 
 
我们注意到，对于自己的门是黑还是白这一单独事件，猜测正确与否概率一定是1/2。但是要求3个人正确2个即可，这就有学问了：最佳策略是要猜错就一起错，但是要正确别一起正确，只要刚好2人正确效率最高！举例说明，三个门颜色方案一共8种，假设全部列出来，共有3*8=24个门的颜色需要ABC来猜。他们只能猜对12次猜错12次，就像手中有12张好牌12张坏牌，每次出3张，有两张好牌算你成功，你会怎么办？当然就是每2次正确1次错误构成一个成功方案，理论上可以推导出：8个方案中最多可以成功6个。 
 
楼上whitetiger的方案小的瑕疵就是三扇门同色时候，出现了3个人都猜对获释的情况，“好牌”利用率不高。楼上Cielo的方案也一样，当白白黑情况出现时，也是“全对”过关，好牌浪费了。 
 
根据以上这道热身题的答案和提示，做这道正题：
思考5个囚徒的策略。

[ 本帖最后由 geslon 于 2008-3-27 07:59 编辑 ]

作者: geslon 时间: 2008-4-8 07:46:30

5个囚徒的策略无人来作？

作者: whitetiger 时间: 2008-4-8 10:49:15

仔细分析了一下，可以从概率上来分析。
 
先分析三人情况。
看到2黑，那么自己的门有3种情况是“白”，有1种情况是“黑”。所以，比较理智的是选择“白”。
看到2白，选择“黑”。
看到1黑1白，自己的门有3种情况是“白”，有3种情况是“黑”。也就是怎么选都是可以的。
我之前的做法，就是确定选一种颜色，3种对，3种错；用geslon的方法，就是选定右侧的颜色，6种都对。当然是geslon的方法占优。
 
再分析五人情况。
看到4黑，自己的门有5种情况是“白”，有1种情况是“黑”，选“白”；
看到4白，选“黑”；
看到3黑1白，自己的门有10种情况是“白”，有5种情况是“黑”，选白；
看到3白1黑，选“黑”；
看到2黑2白，自己的门有10种情况是“白”，有10种情况是“黑”，怎么选都可以（在概率层面上）。
用类似geslon的方法：1、看到颜色有多少，选少的那种；2、2黑2白选右侧。那么，囚徒逃脱的概率是20/32=5/8。
用我的方法：1、看到颜色有多少，选多的那种；2、2黑2白选定黑色。那么，囚徒逃脱的概率是22/32=11/16。
这次又是我的方法占优了。
 
看来这个问题还得研究，特别是对于一般方法。

[ 本帖最后由 whitetiger 于 2008-4-8 11:05 编辑 ]

作者: geslon 时间: 2008-4-8 23:57:12

11/16很好但不够好，还可以更好

作者: Cielo 时间: 2008-4-19 02:14:27

按楼主的方法，一共2^5 * 5 = 160次猜测，其中有一半可以猜对，也就是80次。如果每次都恰3对2错，那可以26/32的概率脱困，但是这样好像很难达到吧。那么考虑5黑和5白这两种情况，每人都猜对，就用掉了10次猜对机会了，然后是4黑1白和4白1黑共10种情况，4个人猜对，就用掉了4 * 10次机会。如果剩下30次可以最高效地利用，可以在30/3中情况中脱困。共22/36的概率。 楼主说可以比这个大，那显然是可以更高效的利用那80次猜对机会咯！期待楼主的答案！

作者: geslon 时间: 2008-4-20 23:37:50

26/32是我的正解，请思考下。再次提高您的效率。

我可以揭底的，不过想必自己想出来更加有成就感。

当然26/32也已经是理论上的最大值了。

作者: Cielo 时间: 2008-4-21 21:33:55

呵呵好吧，不过最近比较忙，可能没时间想，过几天再说吧！ 说不定那时就有人做出来了呢！<img smilieid="1" src="http://bbs.mf8-china.com/images/smilies/default/smile.gif" border="0">

作者: warming 时间: 2008-4-21 21:39:31

好一个难题啊``可以在学校推广啊```

作者: geslon 时间: 2008-4-29 16:13:38

顶上来，期待假日期间有人能解出来。

作者: geslon 时间: 2008-5-13 08:52:12

本周末我来揭底吧！！！！

作者: kexin_xiao 时间: 2008-5-13 10:09:17

等有时间了好好研究，最近有很多这样的问题，快可以出本书了，呵呵

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)