概率趣题之百囚抓号

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

说有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次之前就找到了，他可以停止。再开抽屉失去了意义，因为反正他无法把其余抽屉的信息传递给后来人。

Howard 发表于 2016-12-14 03:46
帮陈爷纠正一个术语使用不当：

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

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

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

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

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

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

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

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

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

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

此处相互独立（independent）事件应该改为互斥（mutually exclusive）事件。所以概率才可以相加。

关于圈，此前多位朋友已经提出“死循环”的说法，意思一样。为了讨论方便以下简称圈。

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

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抽屉）：


更详细资料在此：
https://en.wikipedia.org/wiki/100_prisoners_problem

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

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

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

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

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

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

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

如果允许1号告诉2号的位置，2号找到自己的号码以后随机打开49个抽屉，并且把其他囚徒位置告诉其他囚徒，那样就乱了。是否成功只取决于1号了，1号使用追圈法也没有意义了，与随机打开50个抽屉结果是一样的。所以规则不允许。

Jimihandrix 发表于 2016-12-13 07:28
陈老师，如果规则允许每个囚徒获得之前囚徒的成功信息，那么成功率能提高多少？
...

比如1号囚徒把自己是否成功的信息告诉2号囚徒，2号还是要使用追圈法去找自己的号码。因此，这个信息没有意义。