问题提出
一所监狱的狱长为100名死刑犯提供了最后的挑战机会, 他们的编号从1到100. 一个房间里有100个抽屉，编号也为1到100. 狱长在每个抽屉里随机放一个囚犯的编号, 每个编号都放进了抽屉. 囚犯们一个接一个地进入房间. 每个囚犯可以查看任意50个抽屉. 如果在查看过程中, 每个囚犯都能找到自己的号码, 那么所有囚犯都会被赦免. 如果有一个犯人没有找到自己的号码, 则挑战失败. 在第一个囚犯进入房间之前, 囚犯们可以讨论策略, 但是一旦第一个囚犯进入房间查看, 就不能进行交流. 囚犯们的最佳策略是什么？在这种策略下挑战成功的概率是多少?
如果每个囚犯都随机查看50个抽屉, 那么每个囚犯都有
然而有一种策略, 为囚犯们提供了超过
最佳策略
每个囚犯首先打开与自己的号码相同编号的抽屉.
如果囚犯在抽屉里找到自己的号码, 则挑战成功.
否则, 他在抽屉里找到别人的号码, 然后打开这个号码对应的抽屉.
重复步骤2和3, 直到挑战成功或是查看完50个抽屉.
举个简单的例子, 13号囚犯进入房间后打开13号抽屉. 如果里面是自己的号码则挑战成功, 如果里面是别人的号码, 例如22号, 那么他下一次就需要打开22号抽屉. 以此类推, 直到他找到自己的号码则挑战成功.
下面给出一个成功的例子:
在这个例子中, 13号囚犯一共打开了4个抽屉, 在36号抽屉中找到了自己的号码, 因此挑战成功.
最佳策略下的成功概率
由于100个抽屉中随机放置的是1到100的号码, 因此每个抽屉都正好指向另一个盒子, 也就是说两个盒子不能指向同一个盒子. 由于囚犯从自己号码的盒子开始, 因此, 在经过足够多的步骤后, 他肯定可以找到自己的纸条, 形成一个循环.
比如
就是一个循环, 并且循环长度为4.
因此所有囚徒能够通过挑战, 当且仅当所有循环的长度不超过50, 此时每个囚徒都能在50次以内找到自己的号码.
反之如果有一个循环长度超过50, 那么这个循环上的所有人都会失败。
为了计算“所有循环的长度不超过50”的概率, 利用间接法，先来计算 “有一个循环长度超过50”的概率.
因为“有一个循环的长度是51”和“有一个循环的长度是52”这样的事件是彼此互斥的（循环的长度总和是100）,
所以总概率就是“有一个循环的长度是51”，“有一个循环的长度是52”，..., “有一个循环的长度是100”的概率和.
而对于
从1到100中选出
剩下
因此, 从1到100的数字在长度为
由于总共有
因此在这个策略中, 囚犯大概有
一般情况
如果有
其中
因此
因此无论有多少囚犯, 只要采用上文的策略, 成功的概率就大于