100 个囚犯的随机选择问题


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

  • 有 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 - ($\frac{1}{51}$ + $\frac{1}{52}$ + … + $\frac{1}{100}$) ≈ 0.31183

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

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

参考