100 名囚犯问题——生还率从近乎 0% 跳到 31% 的开箱法

大家好，我是 Senko。本文将解读号称现代逻辑谜题最高杰作的“100 名囚犯问题”。

100 名囚犯被编上 1 到 100 号，另一间屋里摆着 100 个箱子。箱子里各放着一张 1～100 的号码牌，顺序是乱的。囚犯一个一个进屋，最多只能打开 50 个箱子，必须找到写着自己号码的牌。只要有一人失败，全员处决。进屋后不能联络，也不能挪动开过的箱子。全员乱开的话，生还率是二分之一的 100 次方，小数点后排着 30 个零的绝望概率。可只要换一种开法，生还率就会跳到约 31%。

100 名囚犯问题是什么

100 名囚犯问题（英语 100 prisoners problem），是一道具有明明抬不高每个人的成功概率，却能把团队整体的成功概率剧烈抬高这种一时难以置信之结构的概率谜题。先把规则整理一下。

囚犯 100 人，各自被编上 1～100 号
另一间屋里摆着 100 个箱子，里面随机各放一张 1～100 的号码牌
囚犯一个一个进屋，最多能开 50 个箱子。找到自己的号码牌就算成功
开过的箱子要复原关好。不能挪动屋里的东西，也不能留记号
先进去的与后进去的囚犯之间完全不能联络。作战会议只在进屋前开一次
只有 100 人全部成功，全员才被释放

每个囚犯 100 个箱子里只能开 50 个，所以再怎么使巧劲，单人的成功概率也超不过 50%。这个再乘 100 次，生还率事实上是“零”。到这里谁都能推出来，正因如此，这道题的答案才如此震撼。

2003 年诞生的最年轻经典

这道谜题的历史在逻辑谜题里新得异常，出处也很清楚。2003 年，丹麦计算机科学家彼得·布罗·米尔特森在与安娜·加尔合著的论文中提出了它的原型。它本来诞生于考察数据结构极限的理论计算机科学研究。

有意思的是，据说米尔特森自己起初也认为“不存在好的策略”。后来同事斯文·斯库姆找到的策略，漂亮得辜负了专家的预想；到 2006 年，数学家柯廷与沃肖尔更给出了不存在更好策略（即它是最优的）的证明。

此后这道谜题成了数学谜题界的新经典，2022 年一个人气科普视频频道讲了它，于是在大众中爆炸式传开。从诞生到坐上“现代经典”的位子只用了 20 来年，是道少见的“新经典”。

答案是“从自己编号的箱子顺着数字追”

作战单纯得让人泄气。

先打开与自己编号相同的那个箱子。再打开里面那张牌上写的编号的箱子。再打开那张牌上编号的箱子。如此重复 50 次。

比如 28 号囚犯，先开 28 号箱。里面若是 52 号牌，下一个就开 52 号箱。那里若有 7 号牌，下一个开 7 号箱。规则就只是牌上的数字指定下一个要开的箱子而已。

乍看好像与乱开没什么两样。可这种开法里藏着一个决定性的性质：顺着箱与牌的对应追下去，必定总会走到出发点、也就是自己编号的那张牌。从 28 号箱出发的旅程，会在箱子里发现 28 号牌的瞬间结束。也就是说绝对不会迷路。问题只有一个：这趟旅程能不能在 50 步之内结束。

生出 31% 生还率的循环数学

箱与牌的对应，在数学上就是“置换”。而置换必定能分解成若干个环（循环）。若 28 号箱→52 号箱→7 号箱→回到 28 号箱，这三个箱子就构成一个长度为 3 的环。100 个箱子的世界，正好不多不少地分成了这样一堆环。

囚犯所走的旅程，无非就是把自己编号所属的那个环绕上一圈。环的长度在 50 以下，属于这个环的囚犯就全都能在 50 步内走到自己的牌。反过来，只要有一个长度 51 以上的环，那个环里的囚犯就全部失败。

也就是说，全员的命运归结为唯一一个问题：“有没有长度 51 以上的环”

长度 51 以上的环，就算有也只可能有一个（因为 51+51 超过 100）。可以算出，出现长度恰为 k 的大环的概率是“k 分之一”，于是失败概率是 51 分之一到 100 分之一的和，约 69%。因此成功概率约为 31%。就算把囚犯人数继续加大，这个值也只会降到约 30.7%。不管是 100 人还是 100 万人，三成上下的生还率都保得住。

用小例子验一下。囚犯 4 人、箱子 4 个、能开 2 个箱的情形，失败发生在出现长度 3 的环（概率三分之一）或长度 4 的环（概率四分之一）时。合起来是十二分之七，所以成功概率是十二分之五，约 42%。乱开时全员成功是十六分之一（约 6%），可见哪怕只有 4 个人的世界，作战的威力也已经很明显。

个人的命运没变，只是命运的重叠方式变了

这里请回想开头“单人 50% 的墙”。其实就算用了循环策略，每个囚犯的成功概率仍恰好是 50%。自己所属的环长度在 50 以下的概率，一算正好是二分之一。那堵“50% 的墙”一毫米都没被打破。

那到底变的是什么？是成功与失败的重叠方式。乱开策略下，100 人的命运是各自独立的事件，所以全员成功几乎不可能发生。循环策略下，同一个环里的囚犯要么全成功要么全失败，100 人的命运被捆成了几条环。没有长环就全员得救，有长环就一大批一起沉。把失败归拢到全灭那一侧，把成功固化成“全员生还”，于是唯独全员成功的概率暴涨。

这与本系列帽子谜题里介绍的埃伯特帽子游戏，原理完全相同。“胜负的相关性可以设计”——我觉得这个发想通向保险靠捆绑众多投保人的风险而成立的机制，也通向在资产组合里调整各资产联动性的思路，是概率世界的奥义。

为什么要从自己编号的箱子开始

因为把出发点定成自己的编号，所追那个环的终点就必定是自己的牌。顺箱子走的旅程，会在绕环一圈回到出发点之前、也就是在“牌上写着出发点编号的那个箱子”处结束。出发点若是自己的编号，那最后一张牌正是要找的自己的牌。若从随便一个箱子出发，就可能在不含自己牌的环里绕个没完，这份保证也就没了。

如果看守恶意安排号码牌的位置呢

问得尖锐。这个策略出名之后，看守若故意做出长度 51 以上的环，就会全灭。不过有对策：囚犯们事先共享一张“箱子编号的改读表”，全员都经由这个改读去追即可。把囚犯一侧的随机置换叠到看守的布置上，结果又会变成随机置换，约 31% 就复活了。这是用自己一侧的随机数把对方的恶意冲掉，也是密码学里在用的“随机化”思路。

能开的不是 50 个而是 60 个或 30 个呢

成功概率会变成“不存在长度超过那个数的环的概率”。60 个约 49%，70 个可升到约 64%。反过来，能开的数一旦低于一半，长环就可能同时出现多个，计算变复杂，成功率也一口气掉下去。一半即 50 个这个设定，看着绝望其实能救三成，可以说是把惊讶调到最大的绝妙分寸。顺带一提，乱开策略下就算能开 60 个，全员成功的概率是 0.6 的 100 次方，同样事实上为零。