监狱长给犯人们出的难题

小梁

学艺术类的~~~高考数学不算分~~所以数学一塌糊涂~~~~看不明白~~~

lulijie

如何使得看起来是互相独立的事件，变成相互干扰的事件。
我举个例子，希望对大家对本题为什么能大大提高全部成功的概率的理解有帮助。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
有一所监狱，里面有100个犯人。有一天监狱长想了一个难题，他往一个盒子里面随便扔进去一个硬币，然后密闭，固定，使得它的结果不会改变。现在要求犯人们依次来到监狱长的屋子里，告诉监狱长那个硬币是正面还是反面，然后就从这个屋子的另外一个门出去，于是这个犯人没有机会留下信息给后面进来的伙伴。监狱长的难题是要求所有的100人都要猜对，否则就把他们都枪毙了。
现在犯人们可以事先商量一个猜硬币的策略，使得他们能有最大的机会活命，请问他们是怎么做的呢？
－－－－－－－－－－－－－－－－－－－－－－－－－－
如果大家都是随机猜，那么每个犯人的猜对事件相互之间都是互相独立，它们互不干扰，所以它们都发生的概率是(1/2)^100。
如果他们的策略是都猜正面，那么每个犯人的猜对事件相互之间就不是互相独立了，它们要么同猜对、要么同猜错。
也就是说每个犯人的猜对事件原本是互相独立的，经过这个策略，变成了相互干扰，大大提高了它们都发生的概率，从原先的(1/2)^100的概率，提高到1/2 的概率。

骰迷

哇！精采！重點就是捆綁式猜測。

想笑：）

明白了，聪明，佩服……

shadowyang

其实，打开50个盒子后，犯人可以按照他的想法排放这50个签，这样，后面的人就可以比较轻易地找到自己了，第一个人有1/2的机会成功，后面的人第二个人成功的机会>1/2，具体是多少我没算呢，在之后估计前面成功了，后面就100%了，所以能达到30%

Cielo

一直把这个页面存着，但今天才仔细看这题，解法太强了

[ 本帖最后由 Cielo 于 2009-9-22 00:45 编辑 ]

yang_bigarm

原帖由 shadowyang 于 2009-8-26 23:35 发表
其实，打开50个盒子后，犯人可以按照他的想法排放这50个签，这样，后面的人就可以比较轻易地找到自己了，第一个人有1/2的机会成功，后面的人第二个人成功的机会>1/2，具体是多少我没算呢，在之后估计前面成功了，后面 ...

你这分明是在篡改题目嘛。

ggggwhw

1. (*总人数*)
   
2. renshu = 100;
   
3. (*实验次数:*)
   
4. cishu = 10000;
   
5. 
   
6. chenggong = 0;
   
7. For[kk = 1, kk <= cishu, kk++,
   
8. qiutu = {};
   
9. hezi = {};
   
10. haoma = Table[i, {i, 1, renshu}];
    
11. For[ii = 1, ii <= renshu, ii++,
    
12. fanghaoma = RandomInteger[{1, Length[haoma]}];
    
13. AppendTo[hezi, haoma[[fanghaoma]]];
    
14. haoma = Delete[haoma, fanghaoma];
    
15. ];
    
16. For[ii = 1, ii <= renshu, ii++,
    
17. For[jj = 1, jj <= renshu/2, jj++;,
    
18. If[Length[qiutu] < ii,
    
19. AppendTo[qiutu, {hezi[[ii]]}],
    
20. AppendTo[qiutu[[ii]], hezi[[Last[qiutu[[ii]]]]]];
    
21. ];
    
22. If[Last[qiutu[[ii]]] == ii, Break[]];
    
23. ];
    
24. If[jj > renshu/2, Break[]];
    
25. ];
    
26. If[Length[qiutu] == renshu, chenggong += 1(*; Print[qiutu]*);];
    
27. ];
    
28. Print["成功次数" <> ToString[chenggong]];
    
29. Print["实验总次数" <> ToString[cishu]];
    
30. Print["成功的概率" <> ToString[chenggong/cishu // N]];

复制代码

虽然不是很清楚所谓的数字环的理论,但是我觉得这种方法还是不错的.上面是我按照该思想做的Mathematica 程序.当然未必是最短的程序,但是实验次数不是很多时,还是可以出结果的.
成功次数3108
实验总次数10000
成功的概率0.3108
经历的时间是174秒,我还是可以接受这么长时间的.
程序中的(*; Print[qiutu]*)改成Print[qiutu]后可以输出成功时的抽取方法.但是如果实验次数很大时,输出会很长的.如果实验10次成功2~4次那么输出一下可以形象地看出抽取的过程.

[ 本帖最后由 ggggwhw 于 2009-10-21 09:27 编辑 ]

4ky

如果这样，那就有更高概率的做法，每个人记住自己后面的一个人的编号，第一个人打开1-50号箱子，如果后面一个人在这50个箱子里，就把自己的名字换到第1号箱子里，然后如果自己身后的人名字也在这里，就把这个人的名字换到第2号箱子里，如果后面的人的名字不在前50号箱子里，把2号箱子里放上比1号箱子里的号码大的号码，告诉后面一个人，自己看的是前50个箱子，这样后面进来的人，打开第1,2号箱子，如果没有发现自己的名字，如果1>2，就直接在3-50号箱子里找，如果1<2，就在53-100里面找，然后把后面一个人的号码放入第2号箱子，或者用号码的大小通知下一个人应该在哪一半里找自己的名字。

brainyuan

解出来了！
每个犯人先打开自己编号的箱子，如果不是自己，则打开里面名字的犯人编号的箱子，以此类推。
成功概率大于30%，因为100个箱子中出现大于50个元素的循环的概率不超过30%！