百囚問題

每位囚犯必須在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