智游城

标题: 概率趣题之百囚抓号 [打印本页]
作者: Howard    时间: 2016-12-9 07:46
标题: 概率趣题之百囚抓号
本帖最后由 Howard 于 2016-12-11 18:39 编辑

本题在网上有一些讨论（中文的不多），但是希望有兴趣的朋友能独立思考一下，就算想不出思路，思考本身也是有趣的。

说有100个死刑犯，编号为1-100。他们的号码被随机放入100个抽屉。为了活命，他们必须找到写有他们自己号码的纸条。

规则如下：
1. 从1号囚犯开始，按顺序来，每人只能打开50个抽屉。
2. 打开后要关好，后面的人完全看不到前面的人留下的任何信息。
3. 如果所有人都找到了自己的号码，则所有人都活。只要有一个人没找到，全部处死。

游戏开始之前，囚犯们可以商量出一个策略。问：应该采用什么策略？这策略能把所有人的存活率提高到多少？

显然如果没有策略，所有囚犯都随机选择，那么每个囚犯都有50/100也就是1/2的概率找到自己的号码。
（1/2）^100 = 7.89E-31
只有千亿亿亿分之一级别的概率全活下来。( 更正：snowsnow朋友指出，是百万亿亿亿分之一的级别)
---------补充-------------
问：是不是一号囚犯打开一个抽屉，然后二号囚犯打开一个，然后三号囚犯开一个。。。直到所有囚犯都开一个后，再回到1号开第二个。
答：不是。一号囚犯用完所有50个开抽屉机会之后，才轮到2号囚犯。

问：一号囚犯开完了如果没找到，按理所有100囚犯该全部枪毙。如果2号囚犯还有开抽屉的机会，说明1号囚犯找到了他自己的号。
答：所有囚犯都开完了才检验结果，所以每个囚犯并不知道他之前的囚犯成功与否。

问：每个囚犯一定要用完50次机会吗？如果50次之前就找到了自己的号码怎么办？
答：如果50次之前就找到了，他可以停止。再开抽屉失去了意义，因为反正他无法把其余抽屉的信息传递给后来人。









作者: snowsnow    时间: 2016-12-9 08:13
本帖最后由 snowsnow 于 2016-12-9 08:18 编辑

（1/2）^100 = 7.89E-31
只有千亿亿亿分之一级别的概率全活下来。
..........................................................................
是不是最优情况也只有小于1 E－12（万亿分之1）的可能不都给毙了。

作者: 昆仑苍狼    时间: 2016-12-9 08:44
啥意思

1号囚犯 找完之后  2号囚犯知道1号囚犯找到号了吗
作者: Howard    时间: 2016-12-9 09:57
snowsnow 发表于 2016-12-8 18:13
（1/2）^100 = 7.89E-31
只有千亿亿亿分之一级别的概率全活下来。
...................................... ...

符合直觉。 但可能有更好的
作者: Howard    时间: 2016-12-9 09:59
昆仑苍狼 发表于 2016-12-8 18:44
啥意思

1号囚犯 找完之后  2号囚犯知道1号囚犯找到号了吗

2号不知道。每个囚犯进入房间时，房间都是完全一样的状态：抽屉里面仍然按同样顺序放着那些号码，所有抽屉全关。

不用费尽心思去想囚犯之间传递信息的方式，这不是脑筋急转弯。游戏一旦开始，再无信息传递
作者: 昆仑苍狼    时间: 2016-12-9 10:04
Howard 发表于 2016-12-9 09:59
2号不知道。每个囚犯进入房间时，房间都是完全一样的状态：抽屉里面仍然按同样顺序放着那些号码，所有抽 ...

这。。。。

那还有什么策略？

哦 游戏还开始之前他们可以商量

作者: maomaobiao    时间: 2016-12-9 11:31
条件二，打开后要关好，后面的看不到前面人留下的任何信息。

我的思路是，盒子里的条子上作手脚可能么？比如把号码翻过来朝下放回去。
作者: Howard    时间: 2016-12-9 11:33
maomaobiao 发表于 2016-12-8 21:31
条件二，打开后要关好，后面的看不到前面人留下的任何信息。

我的思路是，盒子里的条子上作手脚可能么？比 ...

那还是传递信息。不允许
作者: maomaobiao    时间: 2016-12-9 11:34
看似不能传信息
作者: maomaobiao    时间: 2016-12-9 11:37
这个思路算传递信息么？

1号开1—50号箱子
如果2号仍去开箱，说明1找到了1，因为他们100人没有被立即处死。
作者: Howard    时间: 2016-12-9 12:06
maomaobiao 发表于 2016-12-8 21:37
这个思路算传递信息么？

1号开1—50号箱子

这也算传递信息。为避免此类事发生，可规定100囚犯全部玩过一遍之后再统计结果
作者: maomaobiao    时间: 2016-12-9 13:31
Howard 发表于 2016-12-9 14:06
这也算传递信息。为避免此类事发生，可规定100囚犯全部玩过一遍之后再统计结果 ...

明白了，就是排除一切建立关联的方法
作者: maomaobiao    时间: 2016-12-9 13:35
先猜个答案，思路回头补上

逃脱的概率增加到50^100/（100^50 * 99^50）
作者: 老陈    时间: 2016-12-9 15:10
本帖最后由 老陈 于 2016-12-9 01:16 编辑

如果不是找号码，是猜硬币正反面，情况于此类似。
如果100个囚犯没有策略地猜，那么全部猜对了概率也是千亿亿亿分之一。如果所有囚犯都猜正面，那么他们活下来的概率就是1/2。
上一段是霍爷给我的提示。

霍爷的题目与此有相似之处，如果使用一个策略使每个囚犯找号码的方法不完全独立，就有可能提高全部找对的概率。我根据霍爷的提示找到了一个比较好的策略，如果这些囚徒按我的方法去找自己的号码，他们全部找对的概率大于30%。
作者: 昆仑苍狼    时间: 2016-12-9 16:05
本帖最后由 昆仑苍狼 于 2016-12-9 16:07 编辑

30%？？！！

坐等赐教

第一个囚犯走过去  就只剩50%了。。。

作者: snowsnow    时间: 2016-12-9 16:41
本帖最后由 snowsnow 于 2016-12-9 20:45 编辑

(1/2）^100 = 7.89E-31

..................................
7.89E-31 ~=1E-30.
好像是百万亿亿亿分之一？

作者: maomaobiao    时间: 2016-12-9 21:07
本帖最后由 maomaobiao 于 2016-12-10 06:46 编辑

我的思路是这样的，也是要想办法让每个囚徒的选择建立关联。

1. 如果一个囚徒选择了1-50，另外一个选择了51-100，则这时候逃脱的概率就不是简单的1/2 * 1/2了，而是50/100 * 50/99
由这个思路，我想到如果第三个囚徒选所有单数，第四个囚徒选所有偶数，同样，他们两人同时逃脱的几率也是50/100 * 50/99

2. 另外一个思路是，把一个靶子设为1/100等分的披萨形状，100个囚徒一共选择了100*50次，相当于朝这个靶子一共开了100*50次枪，直觉告诉我们要让这么多枪均匀地分布在靶面上，才能有效的覆盖每一个1/100的扇形区域，从而增加每个区域被击中的几率。那么最好是朝每个扇形区域开了50枪。

3. 结合1和2，最优的方法是

囚徒 1   选择 1-50； 囚徒 2  选择 51-100
囚徒 3   选择 2-51； 囚徒 4  选择 52-100，1
囚徒 5   选择 3-52； 囚徒 6  选择 53-100，1-2
.......
囚徒 99  选择 50-99；囚徒100 选择 100，1-49

选择的区域可以想象一条通过靶心的直线朝一个方向每次位移一格，两个囚徒各选这条直线两边的半圆。

4. 简单的关联，就是 （50/100 * 50/99）^50 的概率逃脱。但是，我发现这样其实可以把1，3， 5....也关联起来。具体没想好怎么算。
作者: 老陈    时间: 2016-12-10 02:24
昆仑苍狼 发表于 2016-12-9 02:05
30%？？！！

坐等赐教


如果后面还有很多囚犯是否找到自己号码与一号囚犯相同，就有可能许多囚犯找完后概率没有发生变化，还是50%。那他们的处境就改善了许多。
作者: Howard    时间: 2016-12-10 06:41
maomaobiao 发表于 2016-12-9 07:07
我的思路是这样的，也是要想办法让每个囚徒的选择建立关联。

1. 如果一个囚徒选择了1-50，另外一个选择了5 ...
如果一个囚徒选择了1-50，另外一个选择了51-100，则这时候逃脱的概率就不是简单的1/2 * 1/2了，而是50/100 * 50/99


这个结论似乎不对。应该还是50/100 × 50/100，也就是1/4。

从宏观角度来看，1-50号抽屉里面有没有1，跟51-100号抽屉里面有没有2，是独立事件，概率都是1/2。

从微观角度细抠，2号囚犯在51-100号抽屉里找2，可以分两种情况：
1、1号囚犯在1-50里面找到了1 （50/100）：
    此时2号囚犯在51-100号抽屉里找到2的概率是50/99 （已经打开的那一个抽屉就不算分母了，只有99个未知抽屉，丫打开50个）
2、1号囚犯在1-50里面没有找到1 （50/100）：
   此时2号囚犯在51-100号抽屉里找到2的概率是49/99 （51-100里面必然有个1，是个废抽屉，不再计算，所以总共99个未知抽屉丫打开49个）

所以二号囚犯的总体成功率是 50/100 × 50/99 + 50/100 × 49/99 = 50/100
作者: snowsnow    时间: 2016-12-10 07:07
如果100个囚犯没有策略地猜，那么全部猜对了概率是千亿亿亿分之一。
-----------------------------------------------------------------------------------------------
答案想不出。
不过100个囚犯没有策略地猜，那么全部猜对了概率是百万亿亿亿分之一。

100,000,000 = 10^8.
亿亿亿 = 10^24.
10^30 应该是 百万亿亿亿
机会还小1000倍。
作者: Howard    时间: 2016-12-10 07:55
snowsnow 发表于 2016-12-9 17:07
如果100个囚犯没有策略地猜，那么全部猜对了概率是千亿亿亿分之一。
------------------------------------ ...

说的挺对 确实是百万亿亿亿分之一的级别
作者: maomaobiao    时间: 2016-12-10 08:03
本帖最后由 maomaobiao 于 2016-12-10 11:36 编辑
Howard 发表于 2016-12-10 08:41
这个结论似乎不对。应该还是50/100 × 50/100，也就是1/4。

从宏观角度来看，1-50号抽屉里面有没有1， ...

1 开1-50，2 开51-100

1先开，2后开。则他们俩开出来各种事件的概率分别是

1不中，2中，50/100 * 49/99；
1不中，2不中， 50/100 * 50/99；
1中，2不中，50/100 * 49/99；
1中，2中，50/100 * 50/99。

四个情况的概率之和 = 1
1中的整体概率=1/2， 2中的整体概率=1/2


1中2也中的概率是 50/100*50/99 ，验证了应该是没错的。
如果2先抓，1后抓，也是同样的。关键就是要把两个人的打靶区域人为地分开。




作者: 老陈    时间: 2016-12-10 09:01
本帖最后由 老陈 于 2016-12-9 19:03 编辑
maomaobiao 发表于 2016-12-9 18:03
1 开1-50，2 开51-100

1先开，2后开。则他们俩开出来各种事件的概率分别是


分母全是100吧，不应该有99。
分子也不应该出现49，50才对吧。
作者: maomaobiao    时间: 2016-12-10 09:09
老陈 发表于 2016-12-10 11:01
分母全是100吧，不应该有99。
分子也不应该出现49，50才对吧。

我修改了一下，应该容易理解了。您再看看
作者: maomaobiao    时间: 2016-12-10 09:33
老陈 发表于 2016-12-10 11:01
分母全是100吧，不应该有99。
分子也不应该出现49，50才对吧。

比方说，如果100个囚犯不是随机选，他们全部都选1-50这50个坑，则他们获救的概率=0

只要有一个坑没有被任何一个囚犯选中，则他们获救的概率 = 0

这是我思路中让每个坑尽量均匀地被覆盖（选中）来提高获救概率的说法。
作者: maomaobiao    时间: 2016-12-10 10:17
本帖最后由 maomaobiao 于 2016-12-10 12:54 编辑

继续之前的思路

囚徒 1   选择 1-50； 囚徒 2  选择 51-100
囚徒 3   选择 2-51； 囚徒 4  选择 52-100，1
囚徒 5   选择 3-52； 囚徒 6  选择 53-100，1-2
.......
囚徒 99  选择 50-99；囚徒100 选择 100，1-49

选择的区域可以想象一条通过靶心的直线朝一个方向每次位移一格，两个囚徒各选这条直线两边的半圆。


-------------------------------------------------------------------

囚徒1 逃脱概率 50/100
囚徒1 和囚徒 2 逃脱 概率 50/100 * 50/99
囚徒1 2 3 逃脱的概率为 50/100 * 50/99 * 50/100
囚徒 1 2 3 4 逃脱的概率为 50/100 * 50/99 * 50/100 * （49 - 2/50^2)/97

有待验证之后找到规律进行计算。
作者: Jimihandrix    时间: 2016-12-10 10:44
本帖最后由 maomaobiao 于 2016-12-10 12:50 编辑

这倒题，换一种说法
100个囚犯，每个囚犯能打开50个抽屉，最多能打开5000次抽屉，求那种打开抽屉组合重复打开抽屉的次数最少

（不好意思，刚才直接编辑了。）
作者: maomaobiao    时间: 2016-12-10 10:51
Jimihandrix 发表于 2016-12-10 12:44
这倒题，换一种说法
100个囚犯，每个囚犯能打开50个抽屉，最多能打开5000次抽屉，求那种打开抽屉组合重复打 ...

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

即便是每一个抽屉被打开了，然而如果不是正确的囚犯打开了正确的抽屉，也是不行的吧？
作者: 老陈    时间: 2016-12-10 11:52
本帖最后由 老陈 于 2016-12-9 22:21 编辑

我们把一个囚犯打开不多于50个抽屉，找到了自己的号码称为成功，否则称为失败。
如果某一个囚犯失败，其它囚犯成功或失败对结果没有影响。但他成功了，其它囚犯成功的意义就非常重要了。如果有一个囚犯能做到你对我就跟着对，你错我就跟着错，那就特别牛了，这次尝试后者不会拖前者的后退。如果不能完全做到，也是越接近越好。
作者: maomaobiao    时间: 2016-12-10 13:29
本帖最后由 maomaobiao 于 2016-12-10 15:32 编辑

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

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

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

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

作者: 老陈    时间: 2016-12-10 13:49
本帖最后由 老陈 于 2016-12-9 23:52 编辑
maomaobiao 发表于 2016-12-9 23:29
囚徒 1   选择 1-50； 囚徒 2  选择 51-100。
他们逃脱的几率



这个思路好了一点点，因为1号必须1-50找到自己的号码，否则2号再找没有意义。但仍不能提高数量级。
作者: maomaobiao    时间: 2016-12-10 14:23
本帖最后由 maomaobiao 于 2016-12-10 16:26 编辑

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

（想得头大，歇会继续）

作者: snowsnow    时间: 2016-12-10 14:40
本帖最后由 snowsnow 于 2016-12-10 15:03 编辑

用排除法。

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

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

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

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

foolproof

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

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

作者: Jimihandrix    时间: 2016-12-10 14:44
本帖最后由 Jimihandrix 于 2016-12-10 15:08 编辑

大致思路是：
一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
第三次开二号抽屉，几号纸条开几号抽屉
二号囚犯第一次开二号抽屉，几号纸条开几号抽屉，第三次开26号抽屉，几号纸条开几号抽屉
三号囚犯第一次开三号抽屉，几号纸条开几号抽屉，第三次开75号抽屉，几号纸条开几号抽屉
作者: snowsnow    时间: 2016-12-10 14:48
本帖最后由 snowsnow 于 2016-12-10 14:57 编辑
Jimihandrix 发表于 2016-12-10 14:44
大致思路是：
一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
第三次开二号抽屉，几号纸条开几号抽屉
一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
二号囚犯第一次开二号抽屉，几号纸条开几号抽屉
....
....
-------------------------
好像可行。
作者: maomaobiao    时间: 2016-12-10 15:43
Jimihandrix 发表于 2016-12-10 16:44
大致思路是：
一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
第三次开二号抽屉，几号纸条开几号抽屉

我觉得这个思路好，应该可以最大程度避免重复开箱。
作者: maomaobiao    时间: 2016-12-10 15:47
Jimihandrix 发表于 2016-12-10 16:44
大致思路是：
一号囚犯第一次开一号抽屉，几号纸条开几号抽屉
第三次开二号抽屉，几号纸条开几号抽屉

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

比如囚犯1开一号抽屉，号码是x，第二次开x号抽屉，抽屉里是1，就卡住了。
作者: Jimihandrix    时间: 2016-12-10 15:58
本帖最后由 Jimihandrix 于 2016-12-10 16:10 编辑
maomaobiao 发表于 2016-12-10 15:47
但是有个问题，如果有死循环呢？

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

可能还没理解这个策略。在这种情况下，等到x号囚犯，他只需开两次抽屉，就能100%开到自己的号码了。这个策略的意义在信息的传递。
1号如果开到自己的号码，2号继续开呗
作者: maomaobiao    时间: 2016-12-10 16:28
本帖最后由 maomaobiao 于 2016-12-10 18:34 编辑
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

接下来呢？


如果不解决互相排斥的问题，仍然会有重复和卡死的情况出现吧？
作者: maomaobiao    时间: 2016-12-10 16:30
Jimihandrix 发表于 2016-12-10 17:58
可能还没理解这个策略。在这种情况下，等到x号囚犯，他只需开两次抽屉，就能100%开到自己的号码了。这个策 ...

信息的传递，不明白。能说仔细一点么？
作者: Jimihandrix    时间: 2016-12-10 18:34
本帖最后由 Jimihandrix 于 2016-12-10 18:35 编辑

如果不能传递信息，那么最佳策略的成功率不会大于（1/2）^100，这题没有意义了。检查了下，修改了下策略。
一号囚犯    第一次开一号抽屉，几号纸条开几号抽屉，一次类推，开到50次为止
二号囚犯    第一次开二号抽屉   如果是一号纸条，一号抽屉100%是二号纸条
                                                           如果不是一号纸条，几号纸条开几号抽屉，开满50次为止
三号囚犯    第一次开三号抽屉   如果是一二号纸条，那么三号纸条100%在一号或者二号抽屉
                                                          不是一二号，几号纸条开几号抽屉，开满50次为止
.
.
.
51号囚犯    第一次开51号抽屉，如果是1-50号纸条，那么51号纸条100%在那个抽屉
                                                   如果不是1-50号纸条，那么51好纸条100%在52-100号抽屉
从51号开始，所有囚犯都能保证开到自己对应的纸条了
大致是这样一个策略。
任何一个囚犯都能将自己开到的纸条信息传递给对应的囚犯。
太累了，逻辑过程先不写了。



作者: snowsnow    时间: 2016-12-10 19:15
本帖最后由 snowsnow 于 2016-12-10 19:20 编辑
Jimihandrix 发表于 2016-12-10 18:34
如果不能传递信息，那么最佳策略的成功率不会大于（1/2）^100，这题没有意义了。检查了下，修改了下策略。
...

Jimihandrix天才的设想。
一号先开一号箱， 一号箱里是几号就去开几号箱。。。。
二号先开二号箱， 二号箱里是几号就去开几号箱。。。。


不会遗漏任何一个线路， 也不会无效重复。

猫兄说的死循环不是坏事， 遇到死循环， 正好是找到了自己的号码。

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

会重复的，你再想想。
作者: karong    时间: 2016-12-10 21:05
感觉上可以这样，1号囚犯开1至50号抽屉，2号囚犯开2至51号抽屉，依此类推，100号囚犯开100号抽屉和1至49号抽屉，这样就能保证所有的抽屉都被开了50次。概率多少不会算。
作者: Howard    时间: 2016-12-11 00:39
maomaobiao 发表于 2016-12-9 18:03
1 开1-50，2 开51-100

1先开，2后开。则他们俩开出来各种事件的概率分别是

对 毛版说的对，是我蒙圈了。本来算的就是二者同时找到的概率。1-50号
作者: snowsnow    时间: 2016-12-11 01:34
Howard 发表于 2016-12-11 00:39
对 毛版说的对，是我蒙圈了。本来算的就是二者同时找到的概率。1-50号

检测一下。
4个犯人／4个盒子的情况。
号码的放法 4!=24  种。
用他的方法有没有> 8种境况可以活？
作者: maomaobiao    时间: 2016-12-11 03:25
karong 发表于 2016-12-10 23:05
感觉上可以这样，1号囚犯开1至50号抽屉，2号囚犯开2至51号抽屉，依此类推，100号囚犯开100号抽屉和1至49号 ...

这个和我的思路一样的。
作者: maomaobiao    时间: 2016-12-11 03:27
snowsnow 发表于 2016-12-11 03:34
检测一下。
4个犯人／4个盒子的情况。
号码的放法 4!=24  种。

你这个算概率的方法不错，能不能归纳法再验证，比我硬算强
作者: maomaobiao    时间: 2016-12-11 04:16
本帖最后由 maomaobiao 于 2016-12-11 10:30 编辑
snowsnow 发表于 2016-12-11 03:34
检测一下。
4个犯人／4个盒子的情况。
号码的放法 4!=24  种。

归纳法试试
---------------------------------
两个囚徒，两个号码。两个囚徒各自只能打开1个抽屉。
如果两个囚徒各自随机打开1个抽屉，有四种组合，概率为1/4，也就是1/2 * 1/2
如果两个囚徒，一个打开1，另一个打开2，则对应的号码摆放有两个组合，概率为 1/2
---------------------------------
四个囚徒，四个号码。四个囚徒各自只能打开2个抽屉。
如果四个囚徒各自随机打开2个抽屉，有（1/2）^4 逃生
如果四个囚徒，一号打开1 2，二号打开 2 3，三号打开 3 4， 四号打开 4 1
用我的思路把顺序重新摆过
一号打开1 2，  三号打开 3 4，
二号打开 2 3， 四号打开 4 1
则一号和三号逃脱的概率为 1/2 * 2/3 = 1/3，而且我们可以惊奇的发现，只要一号和三号逃脱了，则意味着二号和四号必然也能逃脱！(这里经老陈指出，是错误的结论，补充二号逃脱的概率。)

来看二号，承接上面的算法
如果2 3 这两个坑里，0坑被占，意味着 一号 = 1，三号 = 4，二号逃生的概率为 1/4 * 1/3 * 2/2 （#）
如果2 3 这两个坑里，1坑被占，有两种情况
     情况1，一号 = 1，三号 = 3，二号逃生的概率为 1/4 * 1/3 * 1/2 （#）
     情况2，一号 = 2，三号 = 4，二号逃生的概率为 1/4 * 1/3 * 1/2 （#）
如果2 3 这两个坑里，2坑被占，逃生概率为0

把(#)加起来就是 一 三 二 逃生概率 = 1/2 * 1/3 （=2/4 * 2/3 * 1/2）

如果囚徒一二三都逃生了，四号能逃生么？好像还是不能确保
比如纸条的排列是 1 2 4 3，就是一二三都逃生了，但是四号没有逃生的情况。还要算。

来看四号，承接上面的算法
如果4 1 这两个坑里，0坑被占，是不可能的。
如果4 1 这两个坑里，1坑被占，有以下的情况
     情况1，一号 = 1，三号 = 3，二号等于 =2， 四号逃生的概率为 1/4 * 1/3 * 1/2 （&）
     情况2，一号 = 2，三号 = 4，二号等于 =3， 四号逃生的概率为 1/4 * 1/3 * 1/2 （&）
如果4 1 这两个坑里，2坑被占，逃生概率为0


把(&)加和就是一二三四同时逃脱的概率 = 1/4 * 1/3  （= 2/4 * 2/3 * 1/2 * 1/2 ，比 （1/2）^4 高了一点点）

---------------------------------
六个囚徒，六个号码。六个囚徒各自只能打开3个抽屉。
如果六个囚徒各自随机打开3个抽屉，有（1/2）^6 逃生
如果六个囚徒
用以上思路打开
一号打开1 2 3，  四号打开  4 5 6，
二号打开 2 3 4，  五号打开  5 6 1，
三号打开 3 4 5，  六号打开  6 1 2，

一号和四号逃生的几率为 3/6 * 3/5
接下来算一四和二号逃生的几率
  如果2 3 4 这三个坑里，0坑被占，意味着 一号 = 1，四号 = 5or6，二号逃生的概率为 1/6 * 2/5 * 3/4 （#）
  如果 有1个坑被占，有两种情况，第一种：一号 = 2or3，四号=5or6，二号的逃生概率为 2/6 * 2/5 * 2/4 （#）
                                           第二种情况：一号 = 1，四号 = 4，二号的逃生概率为 1/6 * 1/5 * 2/4 （#）
  如果有2个坑被占，意味着一号 = 2or3，四号 = 4，二号的逃生概率为 2/6 * 1/5 * 1/4 （#）

把以上的（#）相加，就是一 四 二号的逃生概率 = 3/6 * 3/5 * 2/4  = 3/20

同之前的道理，只要囚徒 一 四 二 逃脱了，剩下的人必将逃脱（？好像要验证？老陈指出这个不对，还要接着算）
---------------------------------
待续



作者: Jimihandrix    时间: 2016-12-11 05:00
补充一下之前的答案。
一号囚犯    第一次开一号抽屉，几号纸条开几号抽屉，一次类推，开到50次为止
二号囚犯    第一次开二号抽屉   如果是一号纸条，一号抽屉100%是二号纸条
                                                           如果不是一号纸条，几号纸条开几号抽屉，如果开到1号，就去开1号抽屉（1号抽屉100%是2号纸条）开满50次为止
三号囚犯    第一次开三号抽屉   如果是一二号纸条，那么三号纸条100%在一号或者二号抽屉
                                                          不是一二号，几号纸条开几号抽屉，（如果开到1号2号纸条，就去开1号或者2号抽屉）开满50次为止
.
.
.
51号囚犯    第一次开51号抽屉，如果是1-50号纸条，那么51号纸条100%在那个抽屉
                                                   如果不是1-50号纸条，几号纸条开几号抽屉，开到1-50号纸条就去开对应的1-50号抽屉（100%是51号纸条），如果一直开不到1-50号纸条，那么，51号纸条肯定在52-100号抽屉
从51号开始，所有囚犯都能保证开到自己对应的纸条了
大致是这样一个策略。
任何一个囚犯都能将自己开到的纸条信息传递给对应的囚犯。


作者: Jimihandrix    时间: 2016-12-11 05:55
本帖最后由 Jimihandrix 于 2016-12-11 06:02 编辑
maomaobiao 发表于 2016-12-11 04:16
归纳法试试
---------------------------------
两个囚徒，两个号码。两个囚徒各自只能打开1个抽屉。

你的四人策略缺少判断，这是我的四人策略。
囚犯
第一次
抽屉内容
结果
第二次
成功概率
权重

1
一号抽屉
一号纸条
end

50%
25%


二号纸条
二号抽屉
50%
25%


三号纸条
三号抽屉
50%
25%


四号纸条
四号抽屉
50%
25%




50%
2
二号抽屉
一号纸条
end（不解释）

100%
25%


二号纸条
end

100%
25%


三号纸条
推理：

75%
25%


1.一号抽屉肯定不是二号纸条


87.5%
　
2.一号抽屉肯定不是三号纸条


　
3.如果一号抽屉是一号纸条，那么2号纸条在3，4号抽屉


　
4.如果一号抽屉是4号纸条，那么3号抽屉100%是2号纸条


　
5.三号抽屉是二号纸条的概率=50%+（1-50%）*50%=75%
开三号抽屉



四号纸条
类似于三号纸条
开四号抽屉
75%
25%





3
三号抽屉
一号纸条
end

100%
25%


二号纸条
end

100%
25%


三号纸条
end

100%
25%


四号纸条推理：一，二号抽屉肯定不是三号纸条，所以四号抽屉100%是三号纸条　100%25%





100%
4
4号抽屉
一号纸条
end

100%
25%


二号纸条
end

100%
25%


三号纸条
end

100%
25%


四号纸条
end

100%
25%




100%
　


Tatal
43.75%
作者: Jimihandrix    时间: 2016-12-11 06:01
maomaobiao 发表于 2016-12-10 20:05
会重复的，你再想想。

按照这个策略，如果某个囚犯和之前囚犯开的箱子重复了，说明他找到了自己的号码。你仔细想想这个策略。
作者: maomaobiao    时间: 2016-12-11 06:24
Jimihandrix 发表于 2016-12-11 08:01
按照这个策略，如果某个囚犯和之前囚犯开的箱子重复了，说明他找到了自己的号码。你仔细想想这个策略。
...

嗯，我感觉是这样的，没有验证。我在我的思路里继续。

你这个思路我也会算一算，你列的四个囚徒的情况应该容易验算。

你列的表格还没有完全看懂。
作者: 老陈    时间: 2016-12-11 06:28
maomaobiao 发表于 2016-12-10 14:16
归纳法试试
---------------------------------
两个囚徒，两个号码。两个囚徒各自只能打开1个抽屉。

如果四个囚徒，一号打开1 2，二号打开 2 3，三号打开 3 4， 四号打开 4 1
用我的思路把顺序重新摆过
一号打开1 2，  三号打开 3 4，
二号打开 2 3， 四号打开 4 1
则一号和三号逃脱的概率为 1/2 * 2/3 = 1/3，而且我们可以惊奇的发现，只要一号和三号逃脱了，则意味着二号和四号必然也能逃脱！
--------------------------
最后一句不成立吧？
如果：顺序为1432，一号和三号逃脱，二号和四号完蛋。
作者: Jimihandrix    时间: 2016-12-11 06:37
本帖最后由 Jimihandrix 于 2016-12-11 06:39 编辑
老陈 发表于 2016-12-11 06:28
如果四个囚徒，一号打开1 2，二号打开 2 3，三号打开 3 4， 四号打开 4 1
用我的思路把顺序重新摆过
一号 ...

恩，直觉告诉我，没有判断的策略，成功的概率不会大于最大遍历的概率
作者: Jimihandrix    时间: 2016-12-11 06:41
maomaobiao 发表于 2016-12-11 04:16
归纳法试试
---------------------------------
两个囚徒，两个号码。两个囚徒各自只能打开1个抽屉。

求教：
一号打开1 2，  三号打开 3 4，
二号打开 2 3， 四号打开 4 1
则一号和三号逃脱的概率为 1/2 * 2/3 = 1/3

一号和三号逃脱的概率是怎么算出来的？
作者: 老陈    时间: 2016-12-11 06:54
Jimihandrix 发表于 2016-12-10 15:00
补充一下之前的答案。
一号囚犯    第一次开一号抽屉，几号纸条开几号抽屉，一次类推，开到50次为止
二号囚 ...

补充一下之前的答案。
一号囚犯    第一次开一号抽屉，几号纸条开几号抽屉，一次类推，开到50次为止
二号囚犯    第一次开二号抽屉   如果是一号纸条，一号抽屉100%是二号纸条
----------
上面说法不成立。
1号抽屉里号码是3；
2号抽屉里号码是1；
3号抽屉里号码是2。
就不行了。
作者: 老陈    时间: 2016-12-11 07:00
Jimihandrix 发表于 2016-12-10 16:37
恩，直觉告诉我，没有判断的策略，成功的概率不会大于最大遍历的概率

我赞同有关死循环说法那一带的回复，后面的好像越走越远了。
作者: maomaobiao    时间: 2016-12-11 07:07
本帖最后由 maomaobiao 于 2016-12-11 09:08 编辑
Jimihandrix 发表于 2016-12-11 07:55

有点儿最小遍历树的意思
作者: maomaobiao    时间: 2016-12-11 07:11
老陈 发表于 2016-12-11 08:28
如果四个囚徒，一号打开1 2，二号打开 2 3，三号打开 3 4， 四号打开 4 1
用我的思路把顺序重新摆过
一号 ...

是啊，验证一下好像还要再乘一个1/2
作者: Jimihandrix    时间: 2016-12-11 07:31
老陈 发表于 2016-12-11 06:54
补充一下之前的答案。
一号囚犯    第一次开一号抽屉，几号纸条开几号抽屉，一次类推，开到50次为止
二号 ...

上面说法不成立。
1号抽屉里号码是3；
2号抽屉里号码是1；
3号抽屉里号码是2。

陈老师说的这个情况，一号直接就枪毙了。
无论哪种策略，一号囚犯抽到1号纸条的概率永远是1/2，1好50%的失败概率是无法避免的。
这个策略的目的不是将成功率提高到100%（这是不可能的),而是尽可能的提高成功率。
作者: Jimihandrix    时间: 2016-12-11 07:37
老霍说规则规定没抽到暂时不枪毙，等一百人抽完一起枪毙....
我的策略完全错误。
作者: Howard    时间: 2016-12-11 07:55
Jimihandrix 发表于 2016-12-10 17:37
老霍说规则规定没抽到暂时不枪毙，等一百人抽完一起枪毙....
我的策略完全错误。 ...

谢谢不枪毙我！规则不明确，害你浪费那么多时间。回头有电脑了我把楼主贴改一下
作者: maomaobiao    时间: 2016-12-11 08:32
Jimihandrix 发表于 2016-12-11 09:37
老霍说规则规定没抽到暂时不枪毙，等一百人抽完一起枪毙....
我的策略完全错误。 ...

我觉得并不是完全错误，是一个好的思路。即使信息不能传递，你的方法也是一种避免重复开箱的好思路。具体的计算倒不一定简单。
作者: maomaobiao    时间: 2016-12-11 08:35
老陈 发表于 2016-12-11 08:28
如果四个囚徒，一号打开1 2，二号打开 2 3，三号打开 3 4， 四号打开 4 1
用我的思路把顺序重新摆过
一号 ...

我修改了一下。

六个囚犯的，还有得算。但是如果六个的出来了，应该能归纳一下。

至于我这个思路和另外一个Jimi 的思路，哪个能提高生存概率更多，还真不好说。
作者: maomaobiao    时间: 2016-12-11 08:56
本帖最后由 maomaobiao 于 2016-12-11 10:59 编辑

换了一下思路，沿用我之前的那个思路，换一个数学描述，也许会方便计算（也许不会）。

数字1-100，随机分布在编号为 #1 -#100 的坑里
加49个编号为#101-#149的坑，让#101坑里的数字等于#1坑里的数字...#149坑里的数字等于#49坑里的数字。

现在开始有100映射集合，每个集合的大小是50，$1 = {#1 - #50}，...... $100 = {#100 - #149}

问题变了，在这100个映射集合里，每个集合 $X 中，都包含数字 X 的概率是多少？

这和Pizza划分的方法，略有不同。
作者: maomaobiao    时间: 2016-12-11 09:38
把pizza的思路再整理一下，觉得很容易和归纳法结合起来。

一个圆，均匀地分成1-100个扇形。一百个球随机地落入这个圆的扇形区域中。

第一个球Q1 下落，把圆分成两半1-50，51-100，Q1正好落入1-51这个半圆的几率为50/100
第二球 Q2 落入51-100这个半圆的几率为 50/99

然后划分半圆的直径转动一个扇形区域
Q3 落入 2-51 区域
Q4 落入 52 -100，1 这个区域

由于有了Q1和Q2，几率会稍微有点改变
作者: maomaobiao    时间: 2016-12-11 10:08
本帖最后由 maomaobiao 于 2016-12-12 18:49 编辑
maomaobiao 发表于 2016-12-11 11:38
把pizza的思路再整理一下，觉得很容易和归纳法结合起来。

一个圆，均匀地分成1-100个扇形。一百个球随机地 ...

举例简化成一个分成四块的pizza

第一个球落入指定区域的几率为2/4
在此基础上，第二个球落入对面的几率为2/3
转动一下
第三个球要target的区域存在的情况为：
全空 (两个combo)，则意味对面全满，Q4无法落入指定区域，0
一个空位(两个combo)，则意味对面有一个空位，Q3落入指定区域的概率为1/2
全满，同全空。

于是三个球都落入指定位置的概率为2/4*2/3*1/2 * (1/2)注：括号里的1/2是指的对应的combo的情况（2 out of 4)

Q4只能落入剩下的区域。概率同上，则结果和前面计算的结果一样

作者: Howard    时间: 2016-12-12 08:40
已经在楼主贴补充了一些信息，避免误解。
作者: maomaobiao    时间: 2016-12-12 09:53
本帖最后由 maomaobiao 于 2016-12-12 14:05 编辑

如果使用pizza的思路：
两个囚犯逃脱的几率是1/2 （对比完全随机的1/4）
四个囚犯逃脱的几率是2/4 * 2/3 * 1/2 *（1/2）
六个囚犯逃脱的几率是3/6 * 3/5 * 2/4 * 2/3 * 1/2 * （ 8/9 * 10/16）
作者: luckystar    时间: 2016-12-12 12:58
maomaobiao 发表于 2016-12-12 09:53
如果使用pizza的思路：
两个囚犯逃脱的几率是1/2 （对比完全随机的1/4）
四个囚犯逃脱的几率是2/4 * 2/3 *  ...

可能我哪有误解啊。只有两个囚犯逃脱的几率是百分之百啊：一个囚犯打开一个箱子，他的号码在就在，不在就肯定在另外一个箱子啊。
作者: 老陈    时间: 2016-12-12 13:09
luckystar 发表于 2016-12-11 22:58
可能我哪有误解啊。只有两个囚犯逃脱的几率是百分之百啊：一个囚犯打开一个箱子，他的号码在就在，不在就 ...

如果2个囚犯，就只允许打开一个箱子。那就不是100%了。
作者: luckystar    时间: 2016-12-12 13:34
老陈 发表于 2016-12-12 13:09
如果2个囚犯，就只允许打开一个箱子。那就不是100%了。

所以说必须亲眼看见，准确发现在哪一个箱子也不行？不过反正这也不是本题的重点。
作者: notch    时间: 2016-12-12 15:19
全部随机选择就是0.5^2的概率，这是所有选择的平均值
但有一些必死的选择，比如大家都选1~50，或漏一个号码
排除掉这些概率为0的选项能提高剩下选项的平均概率

接下来可能就是要找比平均概率低的选择方案，如果能排除掉也能提高平均值
这个目前还没方向
作者: maomaobiao    时间: 2016-12-12 16:54
notch 发表于 2016-12-12 17:19
全部随机选择就是0.5^2的概率，这是所有选择的平均值
但有一些必死的选择，比如大家都选1~50，或漏一个号码 ...

问题就是，使用一个什么策略，可以尽量避免那些低于平均值的选择。

从这个角度说，Jim的思路可以尽量避免重复，但是不一定能确保选择的逃生成功率高于平均值。
作者: maomaobiao    时间: 2016-12-12 16:58
luckystar 发表于 2016-12-12 15:34
所以说必须亲眼看见，准确发现在哪一个箱子也不行？不过反正这也不是本题的重点。 ...

我没说清楚，两个囚犯两个箱子，每人只能打开一个箱子。条件应该是“找到”自己对应的号码，才能逃生；而不是“知道在哪里”就可以逃生了。

在两个囚犯的情况下，商量好每人打开一个箱子，避免重复打开，肯定是最优策略。而且这个策略和Jim的思路，在两个囚犯的情况下是一致。

Jim的策略在四个囚犯的情况下还没有算。今晚上暴力解决，可以和Pizza策略比较一下。
作者: maomaobiao    时间: 2016-12-12 17:25
Jim 的策略，每个囚犯第一次打开自己编号对应的箱子，如果箱子里的号码不是自己的编号，就打开这个编号对应的箱子。

使用这个策略，在四个囚犯的情况下，惊人地把逃脱成功概率提高到了10/24
比Pizza策略好多了。我接下来会仔细想Jim的这个策略，真的很牛。
作者: maomaobiao    时间: 2016-12-12 17:41
本帖最后由 maomaobiao 于 2016-12-12 19:52 编辑

Jim的策略恰好在于“死循环”。

举例四个囚犯的情况：
比如两个箱子，1 和 4，如果对应的纸条号码是4和1，那么他们俩就可以逃脱。这种循环的size=2

如果箱子 1 对应的纸条号码是 1，其实也是一种“死循环”，循环的size=1

拓展到更多囚犯情况，只要死循环的size小于等于开箱的次数，并且排列的情况被“死循环”给塞满了，就可以逃脱。

---------------------------------------------

继续看四个囚徒的情况：

四个纸条放进四个抽屉，总共有4！=24中组合。在这些组合当中

被size=1的“死循环”塞满的情况，有1种
  1<>1  2<>2  3<>3  4<>4
被两个size=2的“死循环”塞满的情况，有3种
   1<>2<>1   3<>4<>3
   1<>3<>1   2<>4<>2
   1<>4<>1   2<>3<>2
被一个size=2和两个size=1的“死循环”塞满的情况，有6种
   1<>2<>1    3<>3   4<>4
   3<>4<>3    1<>1   2<>2
   1<>3<>1     2<>2   4<>4
   2<>4<>2     1<>1    3<>3
   1<>4<>1    2<>2     3<>3
   2<>3<>2     1<>1    4<>4

总共10种组合可以逃脱，使用Jim策略，在四个囚徒的情况下逃生概率达到10/24
作者: maomaobiao    时间: 2016-12-12 18:16
用Jim策略解决六个囚徒的情况。

六个纸条放进六个箱子，有6!=720种排列组合

其中被size=1的死循环塞满的情况有1种

被三个size=2的死循环塞满的情况有15种（待验证）

被两个size=2和两个size=1的死循环塞满的情况有

被一个size=2和四个size=1的死循环塞满的情况有

被两个size=3的死循环塞满的情况有

被一个size=3，三个size=1的死循环塞满的情况有

被一个size=3，一个size=2和一个size=1的死循环塞满的情况有
作者: Jimihandrix    时间: 2016-12-12 20:45
maomaobiao 发表于 2016-12-12 17:25
Jim 的策略，每个囚犯第一次打开自己编号对应的箱子，如果箱子里的号码不是自己的编号，就打开这个编号对应 ...

哈哈，错进错处，还是猫兄厉害，妙手回春，才能让我的策略发挥预热
作者: Jimihandrix    时间: 2016-12-12 20:49
本帖最后由 Jimihandrix 于 2016-12-12 20:51 编辑
maomaobiao 发表于 2016-12-12 17:41
Jim的策略恰好在于“死循环”。

举例四个囚犯的情况：

10/24这个值与我在允许信息传递规则下策略的成功率只相差2%（43.66%）。
这说明什么呢？
1.这个模型下信息价值很低
2.有信息成功率可以进一步提高，某些线索被我忽略了
作者: 老陈    时间: 2016-12-12 23:08
本帖最后由 老陈 于 2016-12-12 09:23 编辑
maomaobiao 发表于 2016-12-12 04:16
用Jim策略解决六个囚徒的情况。

六个纸条放进六个箱子，有6!=720种排列组合


合计有276种可以逃脱。
8个囚徒，8个箱子。14736种。
作者: snowsnow    时间: 2016-12-13 00:27
先考虑第一步的最优选法。
第一步, 100个囚犯各选不同的箱子。
方便起见按他们的号码选， 1号开1号箱, ..., 100号开100号箱。

其后类推。







作者: bedok    时间: 2016-12-13 02:47
我看了标准答案了，还是令我震惊的。确实是个好题目。
但我想问如果题目变一变，如果打开抽屉的时候只能知道中还是没中，看不到号码，那应该怎么算概率？？
作者: 老陈    时间: 2016-12-13 20:40
我成功地使用圈论和追圈法，把每个囚犯都能在前50次打开抽屉找到自己号码的概率，由随机打开抽屉成功率小到西甘的概率，提高到30%以上。
圈论和追圈法是我为这道题找优化策略时发现的。在我和霍爷的讨论中，霍爷多次指出我论述的谬误之处，最后把谬误的改正，把正确的完善，由我整理贴在这里。圈论和追圈法由霍爷命名。

下面介绍追圈法：
1号囚徒第1次打开1号抽屉，如果发现是1，追圈结束。如果号码不是1，是K1，就打开K1号抽屉，如果发现K1号抽屉里号码是1，追圈结束，如果不是1，下一个就打开发现的这个号码的抽屉。如此找下去。这样就一定在第100次或100次以内找到1号。这个不难理解，因为这100个抽屉里肯定有1号，而且不会打开以前已经打开过的抽屉，因为一个号码不能在多个抽屉里出现。
2号囚徒第1次打开2号抽屉，用和1号囚徒同样策略打开其它抽屉。
M号囚徒第1次打开M号抽屉，用和1号囚徒同样策略打开其它抽屉。
以上就是追圈法。

K1号囚徒打开的抽屉号码是：
K1，K2，...，Kn。
我们把这一串数字成为圈。
Kn号抽屉里的号码是K1。
n是K1号囚徒找到自己号码时打开抽屉的次数。以下称为圈的长度。如果n是51到100，我们称为失败，如果n是1到50，我们称为成功。
显然号码在同一个圈里的囚徒找到自己号码的时打开的抽屉个数相同。

如果失败就是存在长度不小于51的圈。
我们求长度为51的圈出现的概率。有多种方法可以求出，我们介绍3种方法。
方法1:
圈长度为51，意味着K1号囚徒第51次打开抽屉是找到自己的号码。
如果已知圈长度为51，并且K1号囚徒在圈里，那么K1号囚徒出现在位置51的概率为1/51。而K1号囚徒出现在位置51是圈长度为51的充分必要条件，由此得出出现长度为51的圈的概率为1/51。


方法2:
我们随便取51个抽屉，如果随便打开这些抽屉，有51!种打开方式。
打开第1个抽屉，这个抽屉号码为K1，如果抽屉里的号码是其它50个抽屉号码之一，就有可能成为长度为51的圈，把这个号码称为K2。有50种可能。
打开K2号抽屉，这个抽屉里的号码称为K3。如果K3是其它49个号码之一，就有可能成为长度为51的圈。有49种可能。
一直到打开最后一个抽屉，里面的号码是K1，这51个抽屉就成为长度为51的圈。
能够成为长度为51的圈的打开方式有50!种。
由此得出出现长度为51的圈的概率为50!/51!=1/51。与方法1吻合。
那位问了，圈的起点也应该是51吧？答案不是，是1，是最后那个抽屉里的号码。


方法3:
100个抽屉放100个号码，有100!种排列方法。
100个号码取其中51个号码，有C(100,51)种取法。这51个号码成为圈有50!种排列方法，不是51!，因为圈是没头没尾的。其它49个号码有49!种排列方法。那么所有排列含有长度为51的圈的概率为：
C(100,51)*50!*49!/100!=1/51
结果与方法1和方法2相同。(此方法思路由霍爷提供)。


用类似的方法可以求出出现圈长度为52，53，...，100的概率分别是：1/52，1/53，...，1/100。


对于圈长度不小于51的圈，出现不同的圈长度是相互独立的事件，这些概率可以相加。

由此得到K1号由于圈长度而失败的概率为：
F=1/51+1/52+...+1/100

主意：K1和所在的圈里所有囚徒都失败了。并且他们完全相关，命运相同。而不在这个圈里囚徒都不会失败，因为其它所有圈的长度最大是49。

所以F就是所有囚徒没有全部成功的概率。
那么所有囚徒都按追圈法打开抽屉，所有囚徒都能找到自己号码的概率为：
1-F=31.18%


以上结论只在允许打开抽屉个数不小于总抽屉个数的1/2时才成立。比如允许每个囚徒打开40个抽屉，上述结论不成立，因为可能存在2个圈同时失败。




Q&A：
Q：每个囚徒前50次打开抽屉找到自己号码的概率显然是1/2，怎么突然变成31.18%了？
A：这个31.18%不是囚徒前50次打开抽屉找到自己号码的概率，是这个囚徒在长度不大于50的圈的概率。


Q：囚徒在圈里能改变他自己前50次打开抽屉找到自己号码的概率吗？
A：不能。


Q：那成功率为什么不是50%？
A：因为实际打开抽屉时，囚徒不一定打开50个抽屉，找到自己的号码以后再打开其它抽屉没有意义，实际打开抽屉数有可能是1到49中的某一个数，囚徒打开的抽屉数少了，成功率自然变小。再有，这个囚徒虽然成功了，其他囚徒有可能失败，所以总的成功率比50%小是正常的。

Q：1号过去就只剩50%了，最终结果有这么大吗？
A：没错，用追圈法，1号所在的圈的所有人都过去了，成功率并没有改变。这就是追圈法策略的优越之处。

Q：如果囚徒数不是100，而是一个很大的数，由于调和级数是发散的，F值超过1怎么办？
A：不会的。
S(N)=1+½+⅓+¼+...+1/N
当N趋于无穷大时，S(N)也趋于无穷大。
但S(N)-S(N/2)却不是发散的，是收敛的，极限值为ln(2)。
欧拉定理告诉我们：
S(N)-ln(N)当N趋于无穷大时，这个式子趋于一个常数，叫欧拉常数。
所以当N很大时，我们可以认为：
S(N)-ln(N)=S(N/2)-ln (N/2)
都是欧拉常数，由此得到：
S(N)-S(N/2)=ln (N)-ln (N/2)=ln (2)
作者: Jimihandrix    时间: 2016-12-13 21:26
老陈 发表于 2016-12-13 20:40
我成功地使用圈论和追圈法，把每个囚犯都能在前50次打开抽屉找到自己号码的概率，由随机打开抽屉成功率小到 ...

先顶，慢慢看
作者: Jimihandrix    时间: 2016-12-13 21:28
老陈 发表于 2016-12-13 20:40
我成功地使用圈论和追圈法，把每个囚犯都能在前50次打开抽屉找到自己号码的概率，由随机打开抽屉成功率小到 ...

陈老师，如果规则允许每个囚徒获得之前囚徒的成功信息，那么成功率能提高多少？
作者: 老陈    时间: 2016-12-13 21:42
本帖最后由 老陈 于 2016-12-13 07:57 编辑
Jimihandrix 发表于 2016-12-13 07:28
陈老师，如果规则允许每个囚徒获得之前囚徒的成功信息，那么成功率能提高多少？
...


比如1号囚徒把自己是否成功的信息告诉2号囚徒，2号还是要使用追圈法去找自己的号码。因此，这个信息没有意义。
作者: 老陈    时间: 2016-12-13 21:50
本帖最后由 老陈 于 2016-12-13 08:01 编辑


如果允许1号告诉2号的位置，2号找到自己的号码以后随机打开49个抽屉，并且把其他囚徒位置告诉其他囚徒，那样就乱了。是否成功只取决于1号了，1号使用追圈法也没有意义了，与随机打开50个抽屉结果是一样的。所以规则不允许。
作者: Howard    时间: 2016-12-14 01:03
本帖最后由 Howard 于 2016-12-13 11:09 编辑

陈爷确实浑身是数学细菌。五六天前，哥在给陈爷说这道题的时候，叙述完题目之后，哥说，如果3天内能自主想出策略并能准确计算其成功率，智商125。当天就能，智商140。1小时内就行，智商150+

因为哥看完标准答案后，判断自己绝逼无法在3天内想清楚，即使想出策略也无法计算其概率。

没想到陈爷果然在1小时以内就当场说出了正确策略，并采用了跟标准答案不同的解释方法。

哥不信还有这么拽的人，于是追问每一步推理的过程。

果然，在其推理过程中，发现了漏洞。
但是，用错误的推理，怎么能得出正确的结果呢？

这有两个可能：
1. 错误的地方至少有两处，这些错误的地方错进错出，反而导致了正确的结果。拿俗话说，就是瞎猫碰上死耗子了。
2. 已经用直觉掌握了正确的推理，只不过语言暂时没有把这种直觉描述出来。

开始的一两天，我一直以为是第1个可能。但是后来，在经过对推理过程的润色和加工，可以作为完整的推理，我才明白，几乎可以肯定是第2种可能。也就是说，陈爷在得知题目1小时内就自行想出了策略并计算出了完整概率。
有图为证时间戳：

[attach]6204[/attach][attach]6205[/attach][attach]6206[/attach]
作者: Howard    时间: 2016-12-14 01:33
关于圈，此前多位朋友已经提出“死循环”的说法，意思一样。为了讨论方便以下简称圈。

这些事实可以作为陈爷上述证明过程的补充，不是数学意义上的补充，是为了理解起来更方便：

1. 每个号码都在它的圈内。不存在“圈外的号码”
   这一点可能要想几秒钟。

2. 圈与圈之间是没有重合的，不可能一个号码同时在两个或多个圈内。或者说圈之间是disjoint的
  这可能要想几十秒。

3. 100个号码中，最多只能有一个长度超过50的圈。
   由1和2，这一条应该是显而易见的。

4. 所有囚犯成功，当且仅当最大圈长度不超过50。也就是说，这是充分必要条件。
  这可能也要想几分钟或者十几分钟

5. 最大圈长度是51-100的概率计算方法（标准答案）

  设最大圈长度为s （51<=s<=100）
  则有C(100,s)种办法选出这s个最大圈内的数字；
  选出来以后，这s个数字有 (s-1)!种排列方法。（因为是圈，所以是s-1阶乘，如果是队列，则是s！这一点没有接触过圈排列方式的可能要想几十分钟）
  其他100-s个数字随机排列，有(100-s)!种方法
  
  所以一共有C(100,s) * (s-1)! * (100-s)! 种“最大圈为s”的排列方法。
  而100元素的全排列有100!种方法，
  所以最大圈长s的概率是
C(100,s) * (s-1)! * (100-s)!
----------------------------------    =  1/s
                      100!

注意这个计算过程只适用于圈长>=51。上文陈爷也说明了，如果圈长在50以下，则可能有两个甚至多个此长度的圈，计算就复杂得多了。

6. 最后贴一个图说明最大圈长的概率分布（100号码100抽屉）：
[attach]6207[/attach]

更详细资料在此：
https://en.wikipedia.org/wiki/100_prisoners_problem
作者: Howard    时间: 2016-12-14 01:46
老陈 发表于 2016-12-13 06:40
我成功地使用圈论和追圈法，把每个囚犯都能在前50次打开抽屉找到自己号码的概率，由随机打开抽屉成功率小到 ...

帮陈爷纠正一个术语使用不当：

“对于圈长度不小于51的圈，出现不同的圈长度是相互独立的事件，这些概率可以相加。”

此处相互独立（independent）事件应该改为互斥（mutually exclusive）事件。所以概率才可以相加。
作者: 吹牛无罪    时间: 2016-12-14 01:54
老陈 发表于 2016-12-13 20:40
我成功地使用圈论和追圈法，把每个囚犯都能在前50次打开抽屉找到自己号码的概率，由随机打开抽屉成功率小到 ...

老陈以前教数学的？
不然我就太太太佩服了。

作者: 吹牛无罪    时间: 2016-12-14 02:17
Howard 发表于 2016-12-14 01:33
关于圈，此前多位朋友已经提出“死循环”的说法，意思一样。为了讨论方便以下简称圈。

这些事实可以作为陈 ...

4 想了十几分钟，直到我发现囚犯们可以商量好，都从自己的顺序号开始。1号囚犯从第一个开始试，2号从第二个开始试，3号先试第三个......

作者: maomaobiao    时间: 2016-12-14 08:51
Howard 发表于 2016-12-14 03:46
帮陈爷纠正一个术语使用不当：

“对于圈长度不小于51的圈，出现不同的圈长度是相互独立的事件，这些概率 ...

互斥事件，对这道题里概率的提高起到了非常重要的作用。




欢迎光临 智游城 (http://zhiyoucheng.co/) Powered by Discuz! X3.2