geslon难题系列之一：囚徒脱困难题

geslon

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

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

Tain

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

geslon

策略是有的。

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

Tain

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

geslon

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

Cielo

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

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

whitetiger

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

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

Cielo

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

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

geslon

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

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

geslon

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