From live space:

这题以前在math板上出现过，这两天又有人在msn上提了。我重新想了一遍，觉得解法及内在的思路实在是漂亮，特此推荐。

100个囚犯，每人有一个从1到100的不重复不遗漏的号码，国王把这些号码收集起来，打乱放进100个箱子里，每个箱子里有且仅有一个号码。囚犯们一个一个地来到100个箱子面前，每人可以打开至多50个箱子来寻找自己的号码，可以一个一个打开（即可以根据之前箱子里看到的号码来决定后面要打开的箱子）。如果有一个囚犯没有找到自己的号码，那么这100个人一起被处死；只有当所有的囚犯都找到了自己的号码，他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策，但是一但打开了箱子，他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率？

显然，每个人随机选50个箱子打开，存活概率会是1/2的100次方，可以小到忽略不计。但是事实上有一种极简单的办法，其存活概率高达30%-_-，大家想一想:)

这个似乎更像是数学题，其实对于学过抽象代数的人来说，找到这个方法是挺自然的，但是证明是否有更好的解比较复杂。我在84题里提到过全排列都可以写成cycle decomposition的形式，把箱子编号视作原数列，而箱子里的号码视作一个全排列，假如他所在的环的长度不大于n/2，顺着环走总能找到自己的号码。同时有一个环长度大于n/2的概率是

写个小程序就能算出结果小于0.7，即所有环长度不大于n/2的几率大于0.3。