监狱长给犯人们出的难题

lulijie

如果要50%的人成功，可以100%做到。
要100%成功，30%可能做到，关键是如何安排的问题。

lulijie

假设a选择打开的盒子号码与b选择打开的盒子号码有m个号码相同。（0<=m<=50)
那么，a、b都看到自己名字的概率1/2*(50-m)/100+m/100  *  (50-m)/100+m/100 *  (m-1)/100=1/4-m/10000
所以无论如何安排方案，a、b两个人都能成功的概率<=1/4，对于全部100个人，全部成功的概率必然不可能达到楼主所要求的30%。

lulijie

楼主的题目应该是出错了，这是不可能达到的目标。
可以把题目改为：
      如何安排方案，才能使得他们全部成功的概率最大。最大概率是多少？

lulijie

编程模拟一下，结果：
     假设所有人打开箱子的号码方案都是随机，试验10000次，没有一次100个人都成功.
所以觉得100个人都成功的概率应该很低。
-------------------------------------------
假设有100箱子、m个人，每个人可打开50个箱子，这m个人都看到自己的名字的概率为P(m)。
那么楼主的题目就是求P(100)的最大值。
不烦考虑一下，简单的情况。
P(2)最大值=1/4      ，两个人没有相同号码的方案概率最大。
P(3)=？
-----------------------------------
大家可以先求一下P(3)的最大值。这个应该比P(100)简单多了，但也不是看一眼就能得出结果的。
    P(100)的概率应该是个小概率事件。

lulijie

13楼的P(2)的定义和我的不一样，我的定义是100个箱子中有两个箱子中写有这2个人的名字，每个人可以打开50个箱子。

lulijie

3楼的
第一个人选1-50号，概率是1/2，第二个人选51-100号，概率也是1/2，那么他们都选中
自己名字的概率是1/2 x 1/2 = 1/4，就是25%，两个人的情况已经低于30%了吔。
那么100个人的情况怎么办呢？大家想想啊！
----------------------------------------------
我想当然的认为上面没错，结果5#计算的结果也出错。
    第一个人选1-50号，，第二个人选51-100号，那么他们都选中的概率应该等于
      50*50/(100*99)=25/99，不等于1/4，略大于1/4。
------------------------------------------------------
所以5楼的计算结果：
假设a选择打开的盒子号码与b选择打开的盒子号码有m个号码相同。（0<=m<=50)
那么，a、b都看到自己名字的概率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。所以楼主的要求还是不可能达到的

lulijie

可以按照13楼的定义来计算：
  那么随机方案，P(4)的概率并不等于1/16。应该比1/16大。
电脑模拟计算Noski定义的随机方案的P(4)：
模拟1000000次，成功90095次。概率9%左右。

lulijie

重新计算17楼的随机方案P(4)：
电脑模拟1千万次，成功次数920887。概率不等于1/16， 说明每个人选中的事件不是独立事件。

lulijie

对于21楼的质疑，我仔细考虑一下，觉得没理由不是独立事件，得到的概率应该等于1/16。
问题出在哪里?又重新运行多次，得到的概率分别是7.5%、11.2%。波动还挺大的，按理说1千万次的模拟，概率波动不应这么大？真的应该像Noski所说的随机序列生成器出了问题。
每个人随机选号码箱的号码组合，我设计了一个子程序，每运行一下子程序，就随机生成一个号码组合。
这个子程序是，先初始化随机序列生成器(以免每次生成相同的随机数序列)，再运用随机函数，随机生成号码组合。
按理说这个子程序设计应该没问题，但后来证实恰恰是这个子程序出了问题。问题在 初始化随机序列生成器。
因为每个人随机设定他选择的号码组合，都要调用一次那个子程序，而每调用一下子程序，就初始化一次随机序列生成器。
最后造成每个随机数序列都不是完整的，每每被中断。
--------------------------------------------------------------------------
最后删除子程序中的初始化随机序列生成器的语句，将初始化随机序列生成器语句直接放在主程序调用随机函数之前。
重新运行程序，
    1百万次，成功62640次
    1千万次，成功624466次。概率非常接近 1/16=0.625

lulijie

计算p(4)，但如果这三个人约定好，1选1和2，2选2和3，3选3和4，4选4和1，那么这时P(4)就等于1/12?
---------------------------------
电脑模拟：1百万次，成功83375次，非常接近1/12。
P(4)中最大的概率是不是1/12，还有其他方案更佳么？
推广到P(m),概率最大的方案到底如何呢？    P(m)采用noski定义