监狱长给犯人们出的难题

lulijie

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

noski

不知如何证明这个方案是不是最大概率，用Windows自带的计算器算了一下，这100个人的50-50的约定的概率是9.9e-30，比随机选的概率7.9e-31提高了12倍以上，但还是很小的小概率事件。

yang_bigarm

以上说法都没有命中题目的要害．

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个人，楼主的要求更是不可能做到的。

noski

也许前面对半分的策略并不是最好的策略。。

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的概率。
---------------------------------------------------------------------------

noski

一开始我就在怀疑这道题的正确性，想怎么可能把概率从十的负30次方一下子提高到0.3以上，可是这道题却无情的颠覆了我的直觉。。。这么好的解法。。。