五个聪明的囚犯

独木桥 · 发表于 2005-2-19 02:37:42

最近这里比较热闹，高手不少。万精油的囚犯问题非常有趣，让人看了以后感觉收获不小。我也贴一个囚犯问题，很有意思，难度也不小，希望给这里的网虫们带来乐趣。www.ddhw.com

一个监狱里有5个特聪明的犯人，每人都单独关在自己的牢房里，无法和其他囚犯做任何通讯。每天晚上囚犯可以聚在一起自由讨论一次。有天晚上典狱长通知了这么个消息：国王决定集体大赦囚犯，但是要考这些囚犯一个题目：在次日早晨，会有人来把每间牢房门的正面刷上或黑或白的颜色，颜色的选择是等概率独立的（比如用抛硬币的方法决定门上该刷黑还是白色），犯人都不可能知道自己门上被刷了什么颜色。然后犯人会依次被叫到典狱长办公室里。走出牢房时，犯人有机会看见所有其他人门上的颜色，但是因为他自己的牢门是开着的，所以门正面靠着墙，他还是看不见上面的颜色。在办公室里典狱长询问犯人对自己牢门上的颜色是黑是白的猜测。然后犯人被带回牢房，关好门后，下一个犯人再被叫出询问（在典狱长办公室里犯人是看不到前面其他犯人的回答的）。如此直到所有人都被叫出来一次。现在典狱长统计一下所有犯人的猜测，如果猜对自己门上颜色的犯人数过半(也就是3个或3个以上的犯人猜对)，那么他就释放所有犯人，如果不过半，每个犯人都只好把牢继续坐下去。

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

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

问题C:把问题一般化。设有N个犯人（N是奇数），猜对自己门上颜色的犯人数过半，他们就会被释放。他们被释放的可能性最多有多大？

独木桥 · 发表于 2005-2-24 22:08:17

很容易证明最优策略是非随机的. 对于某个人, 给定其他人的策略和门的颜色, 他猜白有一个获胜概率, 猜黑有一个获胜概率. 哪个概率大就裁哪个颜色. 容易看出存在一个非随机策略至少不比随机策略差.

www.ddhw.com

fzy · 发表于 2005-2-24 18:38:42

I tried many different ways for N=5. And I always reached a winning strategy at the end. But I guess this is only true for N=5. For larger N we may need some rules for the choices. Some potential rules may include 1) Keep the choices symmetric; 2) Go for an all wrong answers as early (or as late) as possible. But I believe an optimal strategy always exists. (This is not asked in the original problem.)

I also agree that a deterministic way is better because it is more efficient on using the votes. 0 : 5 and 3 : 2 are more efficient than any non-deterministic way.

QL · 发表于 2005-2-24 06:51:20

"可以证明最优策略是非随机的,"

Is there a simple proof for this?

QL · 发表于 2005-2-24 06:49:29

"In each step, make sure that if they win, they win by a vote of 3 to 2 and if they lose, they lose by a vote of 0 to 5. From the procedure we know that this is optimal."

I guess you have to prove that at each step such arrangment is always possible. After some steps, you may have set decision rules for all the possible 2^4 observations, and you can only hope that for the remaining 5-door possibilities, you only get optimal outcomes when the decision rules are applied.

For N=5, this may not really be a problem, but what about general N?

独木桥 · 发表于 2005-2-22 22:15:59

很显然,任何人无论采用什么策略,他猜对的概率都是1/2.如果猜测是非随机的(任何情况下要么猜白要么猜黑,没有随机猜测),则在 2^N 个基本情形下他将猜对 2^(N-1) 次,猜错 2^(N-1) 次. 因此所有人共猜对 N*2^(N-1) 人次. 要在一种基本情形下获胜, 至少要猜对 (N+1)/2 次, 因此获胜的基本情形数不超过 (N*2^(N-1))/((N+1)/2)=(2^N) *N/(N+1). 成功概率不超过 [(2^N) *N/(N+1)]/2^N. 可以证明最优策略是非随机的, 因此任何策略成功概率不超过这个上限. 找最优策略时尽量做到每种基本情形获胜时比分为(N+1)/2:(N-1)/2,失败时比分为 0:N.

fzy · 发表于 2005-2-22 18:15:06

Assume the five doors form a circle. Therefore every prisoner can see 4 doors from left to right and there are 16 possibilities. This strategy is to select white unless WBBB, BBBW, WBBW, and WWWB. This way they win in 26 of 32 cases, and lose in 6.

The choices are set in a rather simple way: Start from BBBB, and add white doors gradually. In each step, make sure that if they win, they win by a vote of 3 to 2 and if they lose, they lose by a vote of 0 to 5. From the procedure we know that this is optimal.

A computer program should be able to pick the optimal strategy for any N. And the probability is [(2^N)*N/(N+1)]/(2^N)

QL · 发表于 2005-2-21 08:46:30

按提示，先来找上界。

对每一个人来说，看到别人门的颜色并不能对判断自己门的颜色有帮助，因此，每人都有一半的可

能是错的。总体而言，最有效力的安排应当是：在所有2^N情况中，“把猜错尽量集中，把猜对尽量分散”

设上界为X，则：

X (N-1)/2N+ (1-X) = 1/2

X=N/(N+1)

独木桥 · 发表于 2005-2-21 05:42:08

不要放弃. 首先找胜率上界并不困难, 然后再沿着这个思路找最优策略.

husonghu · 发表于 2005-2-21 05:36:12

找最优法和推广到一般的N我就无能为力了。所以此题还大有展身手之处。

独木桥 · 发表于 2005-2-21 05:25:48

我没有仔细check你的方法,这个思路应该work. 其实要找胜率上界不是很难,这个上界是可以达到的.要找到最优方法还要费一点脑筋.

www.ddhw.com

QL · 发表于 2005-2-20 22:57:41

一点想法。

如考虑随机决定：

设第I个人见到J个白门时以P(I，J)的概率猜白，以1-P(I，J)的概率猜黑，

选择P(I，J)，使得总体成功最大。

怎么化简这个复杂的问题？www.ddhw.com

husonghu · 发表于 2005-2-20 22:02:15

因是“依次被叫”，故各人知道自己是第几人被叫的(这个次序也可头天晚上定好)。

猜的策略见下表(说明：4黑0白(猜白)表示见到4黑0白时猜自己门上为白)：

第一人：4黑0白(猜白)、3黑1白(猜黑)、2黑2白(猜白)、1黑3白(猜黑)、0黑4白(猜白)
第二人：与第一人相同
第三人：4黑0白(猜白)、3黑1白(猜白)、2黑2白(猜黑)、1黑3白(猜黑-特别)、0黑4白(猜黑)
第四人：4黑0白(猜白)、3黑1白(猜白)、2黑2白(猜黑)、1黑3白(猜黑-特别)、0黑4白(猜黑)
第五人：4黑0白(猜白)、3黑1白(猜白)、2黑2白(猜黑)、1黑3白(猜黑-特别)、0黑4白(猜白)

与原策略不同之处是在第三、四、五人身上. 原来是3人都用同一策略：
4黑0白(猜白)、3黑1白(猜白)、2黑2白(猜黑)、1黑3白(猜黑)、0黑4白(猜白)www.ddhw.com

现在：
第三人：见到1黑3白时，在一般情况下都猜黑；特别的是，只有见到12345按WW口BW排
列时猜白(W表示white，口表示他自己的位置，B表示black)、见到0黑4白时猜黑；
第四人：见到1黑3白时，在一般情况下都猜黑；特别的是，只有见到12345按WWB口W排
列时猜白、见到0黑4白时猜黑；
第五人：见到1黑3白时，在一般情况下都猜黑；特别的是，只有见到12345按WWWB口
排列或WWBW口排列时猜白、见到0黑4白时仍然猜白。

说明：这样改进后，在不影响到2黑3白成功9种、0黑5白成功1种的前提下，1黑4白
会成功2种(WWBWW和WWWBW)。

这样，
5黑0白的1种会失败；
4黑1白的5种会成功3种；
3黑2白的10种会成功10种；
2黑3白的10种会成功9种；
1黑4白的5种会成功2种(这是改进之处，之前是全失败)；
0黑5白的1种会成功。

在总数32种可能性中，共计25种会成功。

有漏洞吗？还可改进吗？

fzy · 发表于 2005-2-20 20:53:42

In the case of 3黑1白, 2黑2白, and 1黑3白, it can still be refined. For example, for the second person, 3黑1白 with white on the first door and white on the third door are different. His decision should change accordingly. But this is a long chart to fill out. Probably a computer program can help. My guess is the best probability should be in the range of 24/32 to 26/32.

husonghu · 发表于 2005-2-20 08:25:48

因是“依次被叫”，故各人知道自己是第几人被叫的。

猜的策略见下表(说明："4黑0白(猜白)" 表示见到4黑0白时猜自己门上为白)：

第一人：4黑0白(猜白)、3黑1白(猜黑)、2黑2白(猜白)、1黑3白(猜黑)、0黑4白(猜白)
第二人：与第一人相同
第三人：4黑0白(猜白)、3黑1白(猜白)、2黑2白(猜黑)、1黑3白(猜黑)、0黑4白(猜白)
第四人：与第三人相同
第五人：与第三人相同

这样，
5黑0白的1种会失败；
4黑1白的5种会成功3种；
3黑2白的10种会成功10种；
2黑3白的10种会成功9种；
1黑4白的5种全失败；
0黑5白的1种会成功。

在总数32种可能性中，共计23种会成功。

husonghu · 发表于 2005-2-20 06:15:24

同意QL。所以此题不容易。

QL · 发表于 2005-2-20 04:02:45

仍对同一策略不死心。

设以下规则：

若见颜色数差大于2，猜多数颜色。

若见平局，按各1/2 概率随机猜。

若见颜色差等于2，设以概率P猜多数颜色。

然后优化P。好象得了个4次式。

此路通吗？www.ddhw.com

QL · 发表于 2005-2-19 19:01:09

看来都用同一策略不成。

可试试：事先定好，当出现平局(或差二)时，三人猜黑另两人猜白。。。

得静下心来算算。www.ddhw.com

QL · 发表于 2005-2-19 15:59:17

平局，随机。

QL · 发表于 2005-2-19 15:58:17

差2时猜少数的颜色，其他，猜多数。

独木桥 · 发表于 2005-2-19 09:10:33

fzy, 无关,husonghu都答对了问题A,成功率超过50%的策略是存在的. 但是A的推理错在哪里呢?这对如何找最优策略是有启发的. 无关的策略成功率是22/32,已经相当高了,但还不是最高的.

QL · 发表于 2005-2-19 07:42:09

2黑2白是应随机猜，这样，成功概率：
1-2*1/8*C(5，3)/2^N

一般的：

1-2*1/2^K*C(N，K)/2^K

K=(N+1)/2

无关 · 发表于 2005-2-19 07:05:06

被你抢先二十秒，不过，俺觉得还是该猜多数

天生愚笨 · 发表于 2005-2-19 06:58:28

我看懂了～呵呵，真不容易！丁页

husonghu · 发表于 2005-2-19 06:56:14

等概率分布总数=2^5=32种

其中，
0黑5白=1种
1黑4白=5种
2黑3白=10种
3黑2白=10种
4黑1白=5种
5黑0白=1种

可见，2黑3白、或3黑2白的分布数是最多的。所以，猜的策略是：

如看到的黑白数目相同，随便(随机地，如用抛硬币的方法)猜一种；
如看到的黑白数目不同，则猜少的那种。
被释放的可能性=20/32.

N个犯人(N是奇数)时，策略相同，因(N+1)/2 与 (N-1)/2的分布是最多的。
他们被释放的可能性最多有 = 2*C(N,(N-1)/2)/2^N. 不一定超过50%(when N>9)，但这样猜总是最好的。

无关 · 发表于 2005-2-19 06:54:40

for general N, same method applies, with probability of success:

1-C(N,(N+1)/2)/2^N

无关 · 发表于 2005-2-19 06:46:38

按看到门的多数颜色猜：比如看到3黑一白，就猜黑。若看到2黑两白，猜白好了。成功概率：

1-C(5，3)/2^5www.ddhw.com

fzy · 发表于 2005-2-19 06:32:07

For 5 prisoners A is definately false.If a prisoner sees more white (black), he should guess black (white). If same number of white and black, then make a random guess. This way if the colors are 2/3 split (5/8 probability), they have 7/8 chance to win. So the winning probability is 35/64 > 1/2.

The same strategy does not work for large N, because they will lose if the colors are not K / K + 1 split, and for N >= 9, the chance of that split is < 1/2.

		自动登录	找回密码
密码			立即注册

动态微博

五个聪明的囚犯

回复：回复：Excellent[@};-]

回复：回复：回复：五个聪明的囚犯

回复：Excellent[@};-]

回复：回复：五个聪明的囚犯

Excellent[@};-]

回复：五个聪明的囚犯

回复：回复：找最优法和推广到一般的N我就无能为力了。所以此题还大有展身手之处。[:L]

回复：找最优法和推广到一般的N我就无能为力了。所以此题还大有展身手之处。[:L]

找最优法和推广到一般的N我就无能为力了。所以此题还大有展身手之处。[:L]

Very Good!

回复：五个聪明的囚犯

改进，最高成功率25/32，即32种等概率可能性中有25种能保证取胜。不知还能提高否？

Looks like it is possible to improve

5人时，最高成功率23/32，即32等概率可能中有23种能保证取胜。不知还能提高否？

同意QL。所以此题不容易。

回复：回复：回复：回复：五个聪明的囚犯

回复：回复：回复：五个聪明的囚犯

回复：回复：回复：五个聪明的囚犯

回复：回复：五个聪明的囚犯

回复：五个聪明的囚犯

回复：回复：五个聪明的囚犯

回复：回复：五个聪明的囚犯

我看懂了～呵呵，真不容易！丁页

回复：五个聪明的囚犯

回复：回复：五个聪明的囚犯

回复：五个聪明的囚犯

回复：五个聪明的囚犯