监狱长给犯人们出的难题

lulijie

p(4)，方案：1选1、2，2选1、2，3选3、4，4选3、4，
    模拟1百万次，成功167006次，概率接近于1/6。
所以P(4)的最大值不小于1/6。

lulijie

p(6)，方案：第1、2、3个人选1、2、3号码，第4、5、6个人选4、5、6号码，
    模拟1百万次，成功50044次，概率接近于1/20。
比其他方案概率好像都大。
----------------------------------------------
所以我的感觉对于P(m)，最佳方案是：将m个箱子随便平分成两组，一半的人都选这一组号码，另一半人都选另一组号码。这样的方案全部成功的概率最大。最大概率等于1/ C(m,m/2) 。        C(m,2/m)是组合数。
这样P(2)=1/C(2,1)=1/2
       P(4)=1/C(4,2)=1/6
      P(6)=1/C(6,3)=1/20
对于楼主的m=100
   最大概率=1/C(100,50)≈1/10^29
---------------------------------------------------
不知我的感觉对不对。

lulijie

哈哈，楼上的观点和我想法一样阿，不知能不能证明。

lulijie

从2个人的角度来看，当他们选择的号码组没有共同的号码时，2个人都成功的概率最大，我在前面已有计算公式。
对于100个人都成功，应该是他们两两之间共有的号码数目越少越好。
而方案：一半人都选同一组号码，另一半人选另外一组号码。
这样，前一半人与后一半人两两之间就没有相同号码，是不是这样的安排，使得概率会最大呢？

lulijie

不传递信息给后面的人，是不可能做到楼主要求的30%的概率。

lulijie

如果不允许前面的人透漏任何信息（比如调换箱子的位置，调换写有姓名的字条等等）给后面的人，那么
假设第一个人选择打开的盒子号码组与第二个人选择打开的盒子号码组有m个号码相同。（0<=m<=50)
那么，它们都看到自己名字的概率1/2*(50-m)/99+m/100  *  (50-m)/99+m/100 *  (m-1)/99=100/99（1/4-m/10000）
当m等于0时取最大值25/99<30/100。
既然无论如何安排，前两个人都成功的概率已经小于30%，那么对于100个人，楼主的要求更是不可能做到的。

lulijie

只有提高每个人成功的概率才行。 1/2的概率远远不够。
100个囚徒从1到100编号，每个囚徒记住每个人的编号，
每个囚徒进去后，先打开，与自己编号相同的箱子，若找到自己的姓名，就终止。否则，按照箱子中写的名字，换成这个名字囚徒的编号，（这个编号肯定不是该箱子的号码），再打开该编号的箱子，一直进行下去，直到找到自己的名字或不能再打开箱子为止。
这样每个人成功的概率是多少呢？

lulijie

每个人成功的概率一样都是1/2，但前两个人都成功的概率达到37%左右。

lulijie

按照37楼的方法：
比如3号箱子里放的是6号囚徒的名字，6号箱子里放的是11号囚徒的名字，。。。。。。n号囚徒放的是3号囚徒名字。这样上述的数字串构成一个环，3-6-11-......-n-3。
这样，所有的1-100个数字，被分成了若干个环。环中的元素个数从1到100。
假设所有的这些环的元素个数都不大于50，那么按照37楼的方法，必定100个囚徒都能成功找到自己的名字。
如果有一个环的元素个数大于50，那么这个环里的所有相应数字的囚徒都不能找到自己的名字。
-----------------------------------------------------------------------------------------
所以该方法能成功的概率就等于
          将100个数字随机分成若个组（每组的数字排列顺序不同也算不同的情况），所有组的元素个数都不大于50的概率。
---------------------------------------------------------------------------

lulijie

每个人成功的概率都等于1/2，要提高100个人都成功的概率，只有想办法，使得它们成功的情况都碰到一起，失败的情况也尽量遇到一起，这样可以大大提高总概率。
------------------------------------------
比如2个囚徒2个箱子的情况。
每个囚徒成功概率1/2，大家都成功的概率可以提高到1/2。
比如第一个囚徒选1，那么第二个囚徒选2。
这样第一个囚徒若成功，那么第二个囚徒也必然成功，
      第一个囚徒若失败，那么第二个囚徒也跟着失败。
这样只要第一个囚徒成功，两个囚徒也成功，所有概率等于1/2。
这样尽管每个囚徒的概率都等于1/2，但由于把它们成功的情况碰到一起，失败的情况碰到一起，使得每个人成功的时候尽量不浪费掉，所有大大提升了总概率。