百囚犯问题

作者: pdnbplus | 发布时间: 2024/07/13 | 阅读量: 144

百囚犯问题（100 prisoners problem）

问题描述

Philippe Flajolet和Robert Sedgewick在2009年提出了“百囚犯问题（100 prisoners problem）”

一个房间里有100个抽屉，监狱长随意地把1到100这100个号码放入1号到100号抽屉中，每个抽屉一张。囚犯们逐个进入房间，每人可以任意打开50个抽屉，之后关上。如果每名囚犯都在这50个抽屉中发现了他的号码，那么所有的犯人都会被赦免；如果有人没有找到他的号码，那么所有的囚犯都会被处死。在第一个囚犯进入房间之前，囚犯们允许一起讨论开抽屉的“策略”，但一旦第一个囚犯进入房间，他们之间就被禁止交流。

如果随机打开，那么成功的概率为
(12)100=8∗10−31(\frac{1}{2})^{100} = 8 * 10^{-31}

策略选择

每名囚犯进入房间后都——

  1. 先打开自己的号码的抽屉。
  2. 如果这个抽屉里有他的号码，他就成功了。
  3. 否则，抽屉里会有另一个号码，然后他打开这个号码的抽屉。
  4. 不断重复第2步和第3步，直到他找到自己的号码或已经打开了50个抽屉（那就全体失败了）。

这个策略之所以可行：是因为(x,y)(x,y)形成了一个环(用xx表示箱子的号码,yy表示箱子里面装的号码)就是从囚犯自己号码对应的箱子找，总能找到一个箱子有自己的号码；

下证:(x,y)形成了一个环反证：存在某一个路径不成环，设该路径为(x1,y1)→(x2,y2)→⋯→(xn,yn)根据策略的特点有：yk−1=xk该路径不成环：yn≠x1那么(证明在下面给出)：yn=xn−w,(n−w)∈(1,n)又∵yn−w−1=xn−w则表明有两个箱子装着同一个号码，显然不合实际，故(x,y)形成了一个环(从编号x的箱子找，总能在一个箱子中找到编号为x的号码)下证:yn=xn−w,(n−w)∈(1,n)若yn不等于路径中的某一个x，那么一定能将这条路径延长，yn就不是终点yn≠x1且yn≠xn∴yn=xn−w,(n−w)∈(1,n)\begin{aligned} 下证:& (x,y)形成了一个环 \\ 反证：& 存在某一个路径不成环，设该路径为 (x_1,y_1) \to (x_2,y_2) \to \dots \to (x_n,y_n) \\ &根据策略的特点有： y_{k-1} = x_k \\ &该路径不成环： y_n \neq x_1 \\ &那么(证明在下面给出)： y_n = x_{n-w} ,(n-w) \in (1,n) \\ &又\because y_{n-w-1} = x_{n-w}\\ &则表明有两个箱子装着同一个号码，显然不合实际，故(x,y)形成了一个环(从编号x的箱子找，总能在一个箱子中找到编号为x的号码)\\ 下证:& y_n = x_{n-w} ,(n-w) \in (1,n)\\ &若y_n不等于路径中的某一个x，那么一定能将这条路径延长，y_n就不是终点 \\ &y_n \neq x_1 且y_n \neq x_n \\ &\therefore y_n = x_{n-w} ,(n-w) \in (1,n) \\ \end{aligned}

做一个简单的示意图

在这里插入图片描述

在这里插入图片描述

那么很显然，这个环的最大长度决定了囚犯能否获救，如果所有抽屉中的号码恰好构成了长度为100的环，那么显然囚犯会失败；如果有一条长度为49的环、一条长为20、一条为31的环，那么囚犯显然能获救；所以问题的临界情况就在环的长度等于50；

  • 所有的摆放情况(100个不同箱子，塞100个不同的东西,相当于全排列)
    A100100=100!A_{100}^{100} = 100!
  • 最长的环为K(K≥50)K(K\geq50)
    选出K个，在K个箱子里面形成一个环，剩下的100−K在100−K个箱子里全排C100K(K−1)!(100−K)!=100!KP=C100K(K−1)!(100−K)!100!=1K选出K个，在K个箱子里面形成一个环，剩下的100-K在100-K个箱子里全排\\ C_{100}^K (K-1)! (100-K)! = \frac{100!}{K}\\ P = \frac{C_{100}^K (K-1)! (100-K)!}{100!} = \frac{1}{K}

那么所有K≥50K\geq 50的情况都是囚犯没救的情况，有救的情况为
P=1−1100−199−⋯−151=31.2%P = 1-\frac{1}{100}-\frac{1}{99}-\dots-\frac{1}{51} = 31.2\%

拓展到2n个囚犯

即使拓展到2n个囚犯，也是采取相同的策略，则成功概率为
P=1−12n−12n−1−⋯−1n+1P = 1-\frac{1}{2n}-\frac{1}{2n-1}-\dots-\frac{1}{n+1}
根据调和级数的欧拉和
∑n=1k1n=ln⁡k+γ+ϵk\sum_{n=1}^k\frac{1}{n} = \ln k + \gamma +\epsilon_k
其中是γ\gamma欧拉-马歇罗尼常数，而ϵk\epsilon_k约等于12k\frac{1}{2k}，并且随着 kk 趋于正无穷而趋于 0。这个结果由欧拉给出。
P=1−12n−12n−1−⋯−1n+1=1−(12n+12n−1+⋯+1n+1)=1−(12n+12n−1+⋯+11−(1n+1n−1+⋯+11))=1−(ln⁡2n−ln⁡n)=1−ln⁡2=30.68%\begin{aligned} P &= 1-\frac{1}{2n}-\frac{1}{2n-1}-\dots-\frac{1}{n+1} \\ &=1 - (\frac{1}{2n}+\frac{1}{2n-1}+\dots+\frac{1}{n+1}) \\ &=1 - (\frac{1}{2n}+\frac{1}{2n-1}+\dots+\frac{1}{1} - (\frac{1}{n}+\frac{1}{n-1}+\dots+\frac{1}{1})) \\ &=1 - (\ln 2n - \ln n) \\ &=1 - \ln2 = 30.68\% \end{aligned}