一道囚犯的题目zt

新用户

www.ddhw.com

首先要声明的是，这个题目我不知道最佳方案，我也不知道世界上是否有人知道最佳方案，本来我是想拿这个题目写一篇《推而广之》的，后来既然解不出来，那就算了。最佳方案拿不出来，那我就来征求一下比较好的方案。

题目是这样的：

一个监狱里有奇数N个特聪明的犯人，每人都单独关在自己的牢房里，无法和其他囚犯做任何通讯。

每天晚上囚犯可以聚在一起自由讨论一次。有天晚上有个犯人知道了这么个秘密消息：国王决定集体大赦囚犯，但是要考这些囚犯一个题目：

在次日早晨，会有人来把每间牢房门的正面刷上或黑或白的颜色，颜色的选择是同等概率随机的（比如用抛硬币的方法决定门上该刷黑还是白色），犯人都不可能知道自己门上被刷了什么颜色。

然后犯人会依次被叫到典狱长办公室里。走出牢房时，犯人有机会看见所有其他人门上的颜色，但是因为他自己的牢门是开着的，所以门正面靠着墙，他还是看不见上面的颜色。在办公室里典狱长向犯人通知这个大赦的决定，并且询问犯人对自己牢门上的颜色是黑是白的猜测。然后犯人被带回牢房，关好门后，下一个犯人再被叫出询问（在典狱长办公室里犯人是看不到前面其他犯人的回答）。www.ddhw.com

如此直到所有人都被叫出来一次。现在典狱长统计一下所有犯人的猜测，如果猜对自己门上颜色的犯人数过半，那么他就释放所有犯人，如果不过半，每个犯人都只好把牢继续坐下去。

因为N是奇数，所以不会出现恰好一半犯人猜对的可能。现在犯人提前知道了这个消息。有人说，因为他们不能互相通讯，所以看见了其他人的门上颜色，对知道自己门上的颜色毫无用处，即使其他人门上都是黑色，自己门上颜色是白是黑还是可能性各半（因为
每个门的颜色都是单独确定的）。所以无论怎么猜其实就是50%可能性猜对，所以提前知道了这个消息也是白搭。你说这个推理对不对？为什么？

如果你认为这个推理不对，那么犯人们就有机会在一起讨论制定一个策略，使得被释放的可能大于50%。那么如何制定这个策略，使得被释放的可能性尽量大？

 www.ddhw.com

 

  本贴由[新用户]最后编辑于：2006-12-11 19:9:26  

未经注册笔名

如果犯人看见所有其他人门上的颜色, 选颜色多的那种如果一种颜色比另一种多.. 如果黑白一样多, 随机选... 当黑门和白门的个数差的绝对值>=3时, 犯人门被释放.如果差为1, 1-(1/2)^{(N+1)/2}可能被释放... (差肯定是奇数) 当N=1时, 被释放的不可能大于50%...www.ddhw.com

GiveATry

The decision of the prisoners is: If the prisoners come out and see that the majority of doors are white, then every prisoner gives white as the color of his door. That way, more than 50 percent of the prisoners will give the correct color of their doors. If the color is evenly distributed (of course, this would be very rare), the prisoners can decide beforehand to report the same color. This way, the prisoners will have some chance of being correct.

husonghu

2005-2-18，题是独木桥出的，叫<<五个聪明的囚犯>>，包括推广到N个囚犯的情形。当时，本坛的顶级高手独木桥、fzy(也就是现在的constant)、QL、无关等参加了讨论。我呢，也“家犬夹在马群里”跑了一阵，当然是跑不过骏马们的。(我小的时候，喜欢与比我强大的孩子一起玩，常常输得哭鼻子，但又屡败屡战。我外婆就戏称我：“你是家犬夹在马群里跑，怎能跑得过人家呢！”)www.ddhw.com 康斯坦丁(constant)大帝，你能否给大家讲一讲呢？独木桥不在，你最合适担当此任了。要不然，我将引出当时的讨论给大家看看。 我很想念独木桥和其他曾在本坛活跃过的数学高手。记得独木桥上半年来过本坛跟大家打过招呼，说身体不太好，又忙。祝愿他一切都好起来，更希望能再见到他来我们中间(BTW，他是当时从WXC脑坛过来的前辈之一)。

constant

  我看看有没有新想法，有了会写出来，没有就算了

张老师

假设N/2个门是白色，N/2+1个门是黑色，黑色的人出来看到的是等量，所以选事先定好的，假定是白色（50%机会，如果选黑色，黑白门的数目互换，结果一样），那么黑门的选了白色，白门的选了黑色，选错的比选对的多一人。www.ddhw.com

张老师

  失误，按我的说法，没一人选对。