囚徒挑战

问题提出

一所监狱的狱长为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的数字在长度为的循环中的排列方式的数量是

由于总共有的可能排列组合, 则

因此在这个策略中, 囚犯大概有的概率挑战成功.

一般情况

如果有个囚犯, 最优策略下的成功概率为

其中是调和级数的前项. 引入欧拉常数, 则

因此个囚犯在最优策略下的成功概率为

因此无论有多少囚犯, 只要采用上文的策略, 成功的概率就大于.