概率趣题之百囚抓号

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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