概率趣题之百囚抓号

maomaobiao 发表于 2016-12-9 23:29
囚徒 1   选择 1-50； 囚徒 2  选择 51-100。
他们逃脱的几率

这个思路好了一点点，因为1号必须1-50找到自己的号码，否则2号再找没有意义。但仍不能提高数量级。

继续，1 2 3 4 囚徒都逃脱之后，轮到 5 打开 3-52 号抽屉
A 此时3-52号抽屉中0个坑被占的情况，需要满足 囚徒1 3 占据了 1，2号坑 （囚1占了1，囚3占了2），且囚徒 2 4 没有占据51 52坑（囚2没有占51 52，囚4没有占52）。
则此时逃脱的概率为 = 1/100 * 48/99 * 1/98 * 48/97 * 50/96 （#）

B 此时3-52号抽屉中1个坑被占的情况
B-1 囚徒 1 3 占了一个坑，囚徒 2 4 没占坑
      B-1-1 囚徒 1 占了一个坑 （囚1没有占 1 2 号坑），囚徒 2 3 4 没占坑 （囚2没有占 51 52， 囚3 占了2，囚4没有占52，值得注意的是，囚4可以占坑1，因为囚1不在里面，但是囚4的坑里被囚2已经占了一个了，因为囚2不能在51 52坑里。)
            逃率 = 48/100 * 48/99 * 1/98 * 48/97 * 49/96 （#）
      B-1-2 囚徒 3 占了一个坑，囚徒 1 2 4 没占坑。（囚1在 1或2号坑里，囚2没有占 51 52，在53-100的某个坑，囚3 占了3-51 中的某个坑，囚4在53-100并有可能包括坑1 的坑里，考虑囚4的时候，可以认为囚1在1号坑或者2号坑的概率各占一半; 考虑囚4的同时要记住囚2占了一个囚4的坑）
             逃率 = 2/100 * 48/99 * 49/98 * 【1/2* 48/97 + 1/2 * 47/97 】* 49/96 （#）（【】部分 = 50/100 * 96/97）
B-2 囚徒 1 3 没占坑，囚徒 2 4 站了一个坑
      B-2-1 囚徒 1 3 4 没占坑，囚徒 2占了一个坑
      B-2-1 囚徒 1 2 3 没占坑，囚徒 4占了一个坑
C 此时3-52号抽屉中2个坑被占的情况

D 此时3-52号抽屉中3个坑被占的情况

E 此时3-52号抽屉中4个坑被占的情况

（想得头大，歇会继续）

用排除法。

1百万亿亿亿的排列组合只有一个活路。

先考虑排除100%错的选择。

1） 所有人选同50个号，  则100囚徒必死。
N 种排列组合。

2）有一个号所有人都没选， 则100囚徒必死。
M 种排列组合。

foolproof

3）确保100个号码都被选了

4) 确保每人选一个“特定” 号码，
因为每人的“正确”号码必然跟所有人不同。

大致思路是：
一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
第三次开二号抽屉，几号纸条开几号抽屉
二号囚犯第一次开二号抽屉，几号纸条开几号抽屉，第三次开26号抽屉，几号纸条开几号抽屉
三号囚犯第一次开三号抽屉，几号纸条开几号抽屉，第三次开75号抽屉，几号纸条开几号抽屉

Jimihandrix 发表于 2016-12-10 14:44
大致思路是：
一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
第三次开二号抽屉，几号纸条开几号抽屉

一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
二号囚犯第一次开二号抽屉，几号纸条开几号抽屉
....
....
-------------------------
好像可行。

Jimihandrix 发表于 2016-12-10 16:44
大致思路是：
一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
第三次开二号抽屉，几号纸条开几号抽屉

我觉得这个思路好，应该可以最大程度避免重复开箱。

Jimihandrix 发表于 2016-12-10 16:44
大致思路是：
一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
第三次开二号抽屉，几号纸条开几号抽屉

但是有个问题，如果有死循环呢？

比如囚犯1开一号抽屉，号码是x，第二次开x号抽屉，抽屉里是1，就卡住了。

maomaobiao 发表于 2016-12-10 15:47
但是有个问题，如果有死循环呢？

比如囚犯1开一号抽屉，号码是x，第二次开x号抽屉，抽屉里是1，就卡住了 ...

可能还没理解这个策略。在这种情况下，等到x号囚犯，他只需开两次抽屉，就能100%开到自己的号码了。这个策略的意义在信息的传递。
1号如果开到自己的号码，2号继续开呗

Jimihandrix 发表于 2016-12-10 17:58
可能还没理解这个策略。在这种情况下，等到x号囚犯，他只需开两次抽屉，就能100%开到自己的号码了。这个策 ...

重新看了一下，感觉应该会提高概率不少。

一号囚徒

开箱顺序   开箱号码    开出来的号码
1                 1               a
2                 a               b
3                 2               c
接下来呢？

二号囚徒

开箱顺序   开箱号码    开出来的号码
1                 2               c
2                 c               d
3                 26              e

接下来呢？

三号囚徒

开箱顺序   开箱号码    开出来的号码
1                 3               f
2                 f               g
3                 75              h

接下来呢？


如果不解决互相排斥的问题，仍然会有重复和卡死的情况出现吧？

Jimihandrix 发表于 2016-12-10 17:58
可能还没理解这个策略。在这种情况下，等到x号囚犯，他只需开两次抽屉，就能100%开到自己的号码了。这个策 ...

信息的传递，不明白。能说仔细一点么？