监狱长给犯人们出的难题

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?

noski

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

noski

你算的是四个人没有任何约定，每个人都随机的去选的吗？每个人选中的概率是1/2没有异议，那么为什么模拟结果不是1/16呢？
我怀疑是不是计算机中的随机数发生器有规律可循的缘故？

noski

赞！看来一个程序里只要将随机数生成器初始化一次就够了，这可真是一个隐蔽的BUG。。

noski

这个方法比我那个有效，那么来猜测一下：
m为偶数的时候，约定前一半人选前一半的数字，后一半人选后一半的数字，那么概率：
P(m) = (m/2)! * (m/2)! / m!
验证一下：P(2) = 1/2，P(4)=1/6，P(6) = 1/20 ……

noski

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

noski

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

noski

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