百囚犯问题

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

百囚犯问题(100 prisoners problem)

问题描述

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

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

如果随机打开,那么成功的概率为
(12)100=81031(\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)根据策略的特点有:yk1=xk该路径不成环:ynx1那么(证明在下面给出)yn=xnw,(nw)(1,n)ynw1=xnw则表明有两个箱子装着同一个号码,显然不合实际,故(x,y)形成了一个环(从编号x的箱子找,总能在一个箱子中找到编号为x的号码)下证:yn=xnw,(nw)(1,n)yn不等于路径中的某一个x,那么一定能将这条路径延长,yn就不是终点ynx1ynxnyn=xnw,(nw)(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(K50)K(K\geq50)
    选出K个,在K个箱子里面形成一个环,剩下的100K100K个箱子里全排C100K(K1)!(100K)!=100!KP=C100K(K1)!(100K)!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}

那么所有K50K\geq 50的情况都是囚犯没救的情况,有救的情况为
P=11100199151=31.2%P = 1-\frac{1}{100}-\frac{1}{99}-\dots-\frac{1}{51} = 31.2\%

拓展到2n个囚犯

即使拓展到2n个囚犯,也是采取相同的策略,则成功概率为
P=112n12n11n+1P = 1-\frac{1}{2n}-\frac{1}{2n-1}-\dots-\frac{1}{n+1}
根据调和级数的欧拉和
n=1k1n=lnk+γ+ϵk\sum_{n=1}^k\frac{1}{n} = \ln k + \gamma +\epsilon_k
其中是γ\gamma欧拉-马歇罗尼常数,而ϵk\epsilon_k约等于12k\frac{1}{2k},并且随着 kk 趋于正无穷而趋于 0。这个结果由欧拉给出。
P=112n12n11n+1=1(12n+12n1++1n+1)=1(12n+12n1++11(1n+1n1++11))=1(ln2nlnn)=1ln2=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}