一个囚徒问题

shshsh_0510

第二种是先花费100天，然后可以得到一个初始值，从而省掉前面一些人的判断。至于省多少，关键是看首个出现两次的人出现的天数的期望
设p(n)=P{第n-1天还没出现，第n天出现}
则 $p(n)=((100!)/(100^n*(100-(n-1))!))*(n-1)/100$
首个出现两次的人出现的天数的期望 E
$E=\sum_(i=1)^100{p(i)*i=12.2}$
于是平均省掉$\sum_(i=1)^11{100+100/i}=1212.851762天=3.3年$

shshsh_0510

第3种方法分析比较复杂，所以留给大家
我认为二级计数者每个应该在10个左右最好。
另外，这个是目前似乎是最好成绩了，10年左右，是不是还可以更好些呢？还能好多少？

shshsh_0510

12# shshsh_0510

这个题又想了一下，可以设想初始每人有一点的信息，然后通过放下、拾取，信息点开始在人间流动，直到最后有人收集了所有的点才结束。
显然固定一个收集人，则她成为这一过程的瓶颈，所以最好每个人都收集，然后汇总。
但是，收集过程中，往往最后的几人代价很高，所以每人手中的信息点数的不同状态数要尽量小！
想到一种方案，并编程试了一下，3000天可以50%左右的概率成功，所以期望在6000天。不知道他那个10年的是什么样的参数？
我的方法如下：
先两两配对，在X1次后，基本上变成50人有2点，50人0点了，然后再两两配对，X2次后，变成25人，每人4点，....
另外，指定一个收集者，给一定时间Y对剩下的人补漏，最后剩下的6个有16点的人统一由此收集者进行收集

我的参数大概为：
1点 -2 点的合并：700天
2-4：500，然后 100天收集补漏
4-8：400 ，100
8-16：350，100
最后汇总：750

感觉最少不会少于Nlog2N=664,不知道可以有多接近

bolizhou

要能够把时间大量缩短才行，呵呵，看过《Prison Break》电视剧，觉得如果这个时间太久了，那么肯定有那些年纪大的或得了大病的囚徒，会孤注一掷地提前要求释放的。在那个20分钟内，一定有一个像迈克·斯科菲尔德的天才站出来的。