老的囚犯问题

好地方的马甲 · 发表于 2009-9-20 02:13:00

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

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

zgg___ · 发表于 2009-9-21 11:08:21

我所知的最好结果如附件的表，曾在智星上出现过的。

囚徒问题机率表.xls (210 KB, 下载次数: 18)

好地方 · 发表于 2009-9-21 21:03:33

回楼上，这个表我知道，并且我已经得到部分的改进。但我想知道理论上有没有什么突破，比如是否对任意人数和获胜条件，总能达到理论极限的胜率？

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 老的囚犯问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。