近日看到一道题，感觉挺有意思的，和大家分享下。题目的内容是这样的：

• 有 100 个囚犯，每人被随机分配 1 - 100 其中的一个数（无重复）。
• 在另一个房间中有 100 个抽屉，每个抽屉被随机分配了 1 - 100 其中的一个数（无重复）。
• 囚犯只有打开抽屉才能知道抽屉里面的数字。
• 如果该数字正好是自己被分配的数，则顺利通过，下一个囚犯继续找。
• 100 个囚犯每个人都在 50 步（打开一个抽屉算一步）内找到自己的编号，游戏才算赢，才能被释放。
• 游戏过程中抽屉里的数字不会变动，囚犯之间不能互相传递信息，但可以事先商定策略。

囚犯的数是随机分配的，抽屉里的数也是随机放的，看起来很难形成有效策略。如果每个人都按随机打开抽屉的方式去找自己的编号，那么 100 个人都在 50 步内找到自己的数的概率是非常小的。多小呢，我们来算一下：

• 1 个人在 50 步内找到跟自己编号相同的数的概率是 50%（想象把 100 个数字平均分成两堆，每堆 50 个数，自己的编号一定在其中一堆，也就是二选一）
• 100 个人都选对的概率是：0.5 * 0.5 * … * 0.5， 也就是 0.5 的 100 次方，数量级是 10 的 -31 次方，接近普朗克常数的数量级了

如果从地球诞生开始算起，且 1 秒能完成该游戏，那么 45 亿年后的现在， 极大的概率这 100 个囚犯还没有成功完成过一次该游戏。所以盲猜的方式不可取。

每个抽屉有自己的顺序编号，如果把抽屉里的数用来指向下一个抽屉，那么抽屉和抽屉里的数就能形成链表。说来你可能不信，按照这种链表的思路，可以将成功率提高到 30% 以上。

假设某个囚犯抽到的数字是 5，也就是需要在 50 步内，找到放了 5 的那个抽屉。先找到第 5 个抽屉打开，然后看里面的数字是多少，如果不是 5，则找到该数字对应的抽屉再打开，以此类推。

最终要么在 50 步内找到，要么没有。看起来并没有什么特别，为什么成功率能提高那么多呢？

链表有一个重要的概念：环。如果这 100 个数字全部组成一个环，如 1 -> 4 -> 38 -> ... -> 1，那么并不会提高成功率。但如果这 100 个数字形成了多个环，如：

1,5 -> 5,10 -> 10,1 -> 1,5
2,36 -> 36,70 -> 70,8 -> 8,19 -> ... -> 2,36
9,9 -> 9,9 // 序号为 9 的抽屉里，正好放的是 9 这个数字
...

这就有意思了。首先这些链表一定会形成环，因为每一个抽屉里都有一个指针（放的那个随机数），且抽屉的序号可以与随机数完全对应（没有多余，也没有遗漏），所以没有一个抽屉是起点或终点。

再来看，如果某个链表包含的抽屉数小于等于 50 意味着什么？意味着一定可以在 50 次内找到有自己序号的那个抽屉。

假设囚犯拿到的数字还是 5，他打开序号为 5 的抽屉（一定要打开跟自己序号对应的抽屉，不能随机挑一个，可以带着这个问题往下看），然后一路按照数字与抽屉序号这种对应方式，来到了环形链表的最后一个抽屉前，打开它，里面放的就会是想要找的数字：5。

因为环形链表的长度不超过 50，因此抽屉打开次数也必然不超过 50。所以只要只要这 100 个数形成的环形链表中没有一个长度大于 50，按照这个策略，囚犯们就可以全部在 50 步内找到自己的数字。

那接下来的问题就是，这个概率有多大？

除去有一条链表长度大于 50 的情况（不可能存在多条环形链表的长度超过 50，毕竟一共只有 100 个），其他情况都能成功，所以成功的概率就是 1 - 其中一条链表长度大于50的概率。一条链表长度大于 50 的概率，就是把链表长度为 51 到 100 的概率相加。

假设链表的长度为 n(n > 50)，我们来算一下它出现的概率。首先，从 100 个抽屉里任选 n 个抽屉作为产生链表的抽屉，这个有 C(100, n) 种抽法（顺序无关，抽到 1，2，3 号抽屉，和 2，3，1 号抽屉没有区别，所以这里是组合的情况）。

除了选出来的 n 个抽屉，在剩下抽屉里放随机数，有 P(100-n, 100-n) 种放法（顺序相关，所以是排列），也就是 (100-n)! 种。

最后来看看选出来的 n 个抽屉要形成一个环，有几种放法。抽屉里的随机数不是随便放都可以的，比如跟抽屉序号相同的随机数就不能被放到该抽屉中。

假设有 3 个抽屉，就只有两种放法：

1 号抽屉里只能放 2 或者 3，如果放了 2，则 2 号抽屉里只能放 3，如果放了 3，则 3 号抽屉里就只能放 2，因此只有两种放法。

如果是 4 个抽屉有几种放法呢？这个新的抽屉可以出现在原先 3 条链的其中一条链，每出现在其中一条链，就有 2 种放法，所以 4 个抽屉就有 3*2 = 6 种方法形成一个环。

以此类推， 5 个抽屉有 4*3*2 种方法形成一个环，n 个抽屉就有 (n-1)! 种放法。

把这些都乘起来就是长度为 n 的链表的可以摆放的个数：C(100, n) * (100-n)! * (n-1)!，其中 C(100, n) = 100!/((100-n)! * n!)，这个表达式的结果为：100!/n，而这 100 个随机数所有可摆放的个数为：100!，也就是说，链表个数为 n 的可能性为 1/n。

接下来就好办了，把这些可能性排除就是成功的可能性了：

1 - (151 + 152 + … + 1100) ≈ 0.31183

所以，按照这个链表的思路去找自己的号码，就有 30% 以上的概率能够全员通过。

PS: 如果在玩游戏前，可以有一次交换抽屉里随机数的机会，那就可以让胜率达到 100% 了。