100 名囚徒的编号为 1 到 100。另一个房间中放着 100 个关闭的抽屉，也编号为 1 到 100。每个抽屉里随机放着一名囚徒的编号，每个编号只出现一次。

每名囚徒最多可以打开 50 个抽屉，并且必须找到自己的编号。囚徒依次进入房间，搜索开始后不能交流。如果所有人都成功，全员获释；只要有一人失败，所有人都失败。

1234567891011121314151617181920

如果每个人只是随机打开 50 个抽屉，全体成功的概率为 $2^{-100}$，几乎等于零。

囚徒能否提前约定一种策略，让集体成功率变得可观？

提示

每次打开一个

不要让每名囚徒独立随机选择抽屉。

把抽屉中的数字视为一个置换，并沿它的环前进。

所有人成功，当且仅当置换中没有长度超过 50 的环。

解答

认真尝试后再打开

沿置换环前进

编号为 $i$ 的囚徒先打开编号为 $i$ 的抽屉。如果里面是数字 $j$，他就接着打开抽屉 $j$，并以同样的方式继续。

抽屉中的数字构成 $1,2,\dots ,100$ 的一个置换。每个置换都能分解成互不相交的环，囚徒 $i$ 实际上正在沿包含 $i$ 的唯一环行走。只要这个环的长度不超过 50，他就会找到自己。

因此，全员成功当且仅当随机置换中 没有长度超过 50 的环。

对于 $k>50$，一个置换最多只能含有一个长度为 $k$ 的环，它出现的概率是 $1/k$。所以

$$P(\text{成功})=1-\sum _{k=51}^{100}\frac{1}{k}\approx 0.31183.$$

这个共同策略把全员成功的概率，从约 $7.9\times {10}^{-31}$ 提高到了 31% 以上。

关键不只是成功率提高，而是囚徒创造了相关性：他们倾向一起成功或一起失败，这恰好适合题目的集体判定规则。