100囚徒集徽章

056254628

有一天，国王决定实行大赦，给100个囚徒每人发了一个徽章。这100个囚徒关在独立的房间里，每天随机有2个囚徒可以同时放风，放风时，这两个囚徒可以相互交换徽章，放风结束后，2个囚徒将回到自己的房间，留在放风场所里的东西将被清空。若某囚徒集齐了所有的100个徽章，大家将被释放。
问什么策略下，囚徒被释放的天数期望值最小，其精确的期望值T(100)为多少？

056254628

我的策略：放风时，手中徽章少的囚徒将自己的所有徽章都交给对方，徽章一样多的，随便选一个囚徒将他的所有徽章都交给对方。
用电脑模拟100囚徒放风过程，模拟10000次后，平均天数为9748.4804.


根据以上策略，若囚徒总人数n为2，那么第1天放风，将集齐所有的徽章，所以期望值T(2)=1.

KeyTo9_Fans

正解应该是$(1+...+99)*(2-1/100)=4950\times 1.99=9850.5$。

能否多模拟几下，看看误差是否会变小？

#####

你是对的，应该是$(1+...+99)*(2-2/100)=4950\times 1.98=9801$。

056254628

我觉得T（n）=(n-1)^2
T(100)=99^2=9801

gogdizzy

按照楼主给的策略：

第一次合并期望$\binom{100}{2} / \binom{100}{2}$
第二次合并期望$\binom{100}{2} / \binom{99}{2}$
...
第99次合并期望$\binom{100}{2} / \binom{2}{2}$

加起来得( 100 * 99 ) * ( 1/99 - 1/100 + 1/98 - 1/99 + ... + 1/1 - 1/2 ) = ( 100 * 99 ) * ( 1 - 1/100 ) = 9801

所以楼主的公式是对的。