百囚问题

每位囚犯必须在100个抽屉中找到自己的号码，但只能开启50个抽屉

百囚问题（英语：100 prisoners problem）是一个概率论和组合数学中的数学问题。在这个问题中，100名有编号的囚犯必须在100个抽屉中找到各自的号码才能生存下来。规则规定，每位囚犯只能开启50个抽屉，且不能与其他囚犯沟通。乍看之下，这种情况似乎无望，但一个巧妙的策略为囚犯们提供了一个现实的生存机会。

丹麦计算机科学家Peter Bro Miltersen于2003年首次提出了这个问题。

问题

百囚问题在文献中有不同的呈现版本。以下版本是由菲利普·弗拉若莱和罗伯特·塞奇威克提出的：

一所监狱的所长给予100名死刑犯（编号1至100）最后一次机会。一个房间内有一个带有100个抽屉的柜子。所长随机在每个关闭的抽屉中放入一个囚犯的号码。囚犯们一个接一个地进入房间。每位囚犯可以按任意顺序打开并查看50个抽屉。之后抽屉再次关闭。如果在搜索过程中，每个囚犯都在其中一个抽屉中找到了他们的号码，则所有囚犯都将被赦免。如果哪怕一位囚犯没有找到他们的号码，所有囚犯都将死亡。在第一位囚犯进入房间查看抽屉之前，囚犯们可以讨论策略——但一旦第一位囚犯进入后就不得沟通。囚犯们的最佳策略是什么？

如果每位囚犯独立且随机地选择50个抽屉，单个囚犯找到其号码的概率是50%。所有囚犯都找到他们号码的概率是单个概率的乘积，即(1/2)¹⁰⁰ ≈ 6969800000000000000♠0.0000000000000000000000000000008，一个微不足道的小数。情况看起来似乎无望。

解决方案

策略

令人惊讶的是，有一个策略提供了超过30%的生存概率。成功的关键在于囚犯们不必事先决定开哪些抽屉。每位囚犯可以利用从已经打开的每个抽屉中获得的信息来决定下一个要打开的抽屉。另一个重要的观察是，这种方式下，一位囚犯的成功并非独立于其他囚犯的成功，因为他们都依赖于数字的分布方式。

要描述策略，不仅囚犯，抽屉也从1至100编号；例如，从左上角的抽屉开始，逐行编号。策略如下：

1. 每位囚犯首先打开标有他们自己号码的抽屉。
2. 如果这个抽屉包含他们的号码，他们就完成了并且成功了。
3. 否则，抽屉包含另一个囚犯的号码，他们接下来打开标有此号码的抽屉。
4. 囚犯重复步骤2和3，直到他们找到自己的号码，或因为在前五十个打开的抽屉中没有找到而失败。

如果囚犯可以这样无限地继续下去，他们将不可避免地回到他们开始的抽屉，形成一个排列循环（见下文）。通过从他们自己的号码开始，囚犯确保他们处于包含他们号码的特定抽屉循环中。唯一的问题是是否有循环长于五十个抽屉——而且这种可能太长的循环只有一个，因为超过总抽屉一半的数量。

示例

这是一个有前途的策略，以下例子使用了8名囚犯和抽屉，其中每位囚犯可以开4个抽屉来说明。监狱所长以以下方式分配了囚犯的号码到抽屉中：

抽屉号码	1	2	3	4	5	6	7	8
囚犯号码	7	4	6	8	1	3	5	2

现在囚犯这样行动：

• 囚犯1首先打开抽屉1并找到号码7。然后打开抽屉7并找到号码5。然后打开抽屉5，在那里找到自己的号码并成功了。
• 囚犯2按此顺序打开抽屉2、4和8。在最后一个抽屉中找到自己的号码，2。
• 囚犯3打开抽屉3和6，在那里找到自己的号码。
• 囚犯4打开抽屉4、8和2，在那里找到自己的号码。这是囚犯2遇到的同一循环，囚犯8也将遇到。这些囚犯中的每一位都将在第三个打开的抽屉中找到自己的号码。
• 囚犯5到7也都以类似的方式找到了他们的号码。

在这种情况下，所有囚犯都找到了他们的号码。然而，结果并不总是如此。例如，对抽屉5和8的号码进行微小更改将导致囚犯1在打开1、7、5和2（并未找到自己的号码）后失败：

抽屉号码	1	2	3	4	5	6	7	8
囚犯号码	7	4	6	8	2	3	5	1

而在以下安排中，囚犯1打开抽屉1、3、7和4，仍未找到自己的号码：

抽屉号码	1	2	3	4	5	6	7	8
囚犯号码	3	1	7	5	8	6	4	2

事实上，除了6号（他直接成功）外，所有囚犯都失败了。

排列表示

排列的图形表示（1 7 5）（2 4 8）（3 6）和（1 3 7 4 5 8 2）（6）

监狱所长将囚犯号码分配给抽屉的行为，可以用数学上将数字1到100的排列来描述。这样的排列是从1到100的自然数集到其自身的一一对应映射。重复应用排列组合后又回到第一个数字的数字序列称为排列的一个循环。每个排列都可以分解为互不相交的循环，即没有共同元素的循环。上面第一个例子的排列可以用循环表示法写成

$(1~7~5)(2~4~8)(3~6)$

因此由两个长度为3的循环和一个长度为2的循环组成。第三个例子的排列相应地是

$(1~3~7~4~5~8~2)(6)$

由一个长度为7的循环和一个长度为1的循环组成。循环表示法不是唯一的，因为长度为$l$的循环可以用$l$种不同的方式写出，取决于循环的起始数字。在上述策略中打开抽屉时，每个囚犯遵循一个总是以他们自己的号码结束的单一循环。在八名囚犯的情况下，这种遵循循环的策略仅在排列的最长循环长度最多为4时才成功。如果一个排列包含长度5或更长的循环，那么在四步之后没有找到自己号码的所有囚犯的号码都位于这样的循环中。

成功概率

随机排列数字1到100的最长循环长度的概率分布。绿色区域对应于囚犯的生存概率

在初始问题中，如果排列的最长循环长度最多为50，则100名囚犯都能成功。因此，他们的生存概率等于随机排列数字1到100不包含长度大于50的循环的概率。这个概率确定如下。

数字1到100的排列最多只能包含一个长度$l>50$的循环。这样一个循环的数字有确切的${\tbinom {100}{l}}$种选择方式（见组合）。在这个循环中，这些数字可以以$(l-1)!$种方式排列，因为由于循环对称，有$l$种排列可以表示长度为$l$的不同循环。剩余的数字可以以$(100-l)!$种方式排列。因此，带有长度$l>50$的循环的数字1到100的排列数量等于

${\binom {100}{l}}\cdot (l-1)!\cdot (100-l)!={\frac {100!}{l}}.$

一个（均匀分布的）随机排列不包含长度大于50的循环的概率，通过单一事件公式和对立事件公式计算得出

$1-{\frac {1}{100!}}\left({\frac {100!}{51}}+\ldots +{\frac {100!}{100}}\right)=1-\left({\frac {1}{51}}+\ldots +{\frac {1}{100}}\right)=1-(H_{100}-H_{50})\approx 0.31183,$

其中$H_{n}$是第$n$个调和数。因此，使用遵循循环的策略，囚犯在31%的情况下能够生存。

渐近性

调和数近似由双曲线下的面积给出，因此可以通过对数来逼近

如果考虑的是$2n$而不是100名囚犯，其中$n$是任意自然数，那么囚犯使用遵循循环策略的生存概率由以下公式给出

$1-(H_{2n}-H_{n})=1-(H_{2n}-\ln 2n)+(H_{n}-\ln n)-\ln 2.$

已知欧拉-马斯刻若尼常数$\gamma$，对于$n\to \infty$

$\lim _{n\to \infty }(H_{n}-\ln n)=\gamma$

成立，得出一个渐近生存概率

$\lim _{n\to \infty }(1-H_{2n}+H_{n})=1-\gamma +\gamma -\ln 2=1-\ln 2\approx 0.30685.$

由于概率序列是单调递减的，无论囚犯的数量如何，使用追踪循环策略的囚犯生存概率都在30%以上。

最优性

2006年，Eugene Curtin和Max Warshauer证明了遵循循环策略的最优性。证明基于与一个相关问题的等价性，其中所有囚犯都被允许在房间内并观察抽屉的开启。数学上，这种等价性基于Foata转换引理，即（典型的）循环表示法和排列的单行表示法之间的一一对应。在第二个问题中，生存概率与原始问题中使用遵循循环策略的生存概率相同，且不依赖于选择的策略。由于原始问题的任意策略也可以应用于第二个问题，但在那里无法获得更高的生存概率，因此遵循踪循环策略必然是最优的。

另见

• 囚徒困境
• 意外绞刑悖论

书目

• Philippe Flajolet, Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, ISBN 978-1-139-47716-1 
• Richard P. Stanley, Algebraic Combinatorics: Walks, Trees, Tableaux, and More, Undergraduate Texts in Mathematics, Springer, 2013, ISBN 978-1-461-46998-8 
• Peter Winkler, Mathematical Mind-Benders, Taylor and Francis, 2007, ISBN 978-1-568-81336-3