监狱长给犯人们出的难题

lulijie

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

catq2000

这个问题有点难，不理解……

noski

对于两个人的情况，如果这两个人都随机去选，是独立事件，那么p(2)是1/4；如果这两个人约定好，选不同的号码，那么这时P(2)就等于1/2。
对于四个人的情况，随机选的概率p(4)是1/16，但如果这三个人约定好，1选1和2，2选2和3，3选3和4，4选4和1，那么这时P(4)就等于1/12?

schuma

还是得让囚犯能有什么方法来传递信息，比如允许他们重新排列盒子之类的，否则每个囚犯发生的事情都是独立的，这道题就没什么意思了

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%左右。

noski

boy31几是不是一个系列呢。。
如果可以留信息的话，每个人只要给身后的人留1 bit 的信息就够了：
比如第一个人选前50个，如果他告诉身后的人是1，那么让身后的人也选前50个，否则就选后50个。这样概率就能达到50%，只要第一个人中了就行了。
当然这1bit 的信息可以用咳嗽一声或惨叫一声来代替

lulijie

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