概率趣题之百囚抓号

Jimihandrix 发表于 2016-12-10 12:44
这倒题，换一种说法
100个囚犯，每个囚犯能打开50个抽屉，最多能打开5000次抽屉，求那种打开抽屉组合重复打 ...

嗯，有没有可能在这种组合条件下，重复打开的次数最少，但是有一个抽屉仍没有被打开呢？

即便是每一个抽屉被打开了，然而如果不是正确的囚犯打开了正确的抽屉，也是不行的吧？

囚徒 1   选择 1-50； 囚徒 2  选择 51-100。
他们逃脱的几率

我换一个方法解释这个思路：

囚徒1打开抽屉，就好比编号为1的球随机落入1-100个洞里，1号球落入1-50这个区域的概率为50/100

接下来囚徒2打开抽屉，就好比编号为2的球随机落入剩下的99个洞里，2号球落入51-100这个区域的概率为50/99

继续，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个坑被占的情况

（想得头大，歇会继续）

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

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

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

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

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

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%开到自己的号码了。这个策 ...

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

snowsnow 发表于 2016-12-10 21:15
Jimihandrix天才的设想。
一号先开一号箱， 一号箱里是几号就去开几号箱。。。。
二号先开二号箱， 二号箱 ...

会重复的，你再想想。

karong 发表于 2016-12-10 23:05
感觉上可以这样，1号囚犯开1至50号抽屉，2号囚犯开2至51号抽屉，依此类推，100号囚犯开100号抽屉和1至49号 ...

这个和我的思路一样的。

snowsnow 发表于 2016-12-11 03:34
检测一下。
4个犯人／4个盒子的情况。
号码的放法 4!=24  种。

你这个算概率的方法不错，能不能归纳法再验证，比我硬算强