1001个带锁的箱子之解答

问题如下：

“有1001个带锁的箱子，每个锁有1把钥匙，现在这些钥匙随机装在这些箱子里，箱子锁着，而且每个箱子里恰好有一把钥匙。随意挑其中的19个箱子砸开，问通过这19把钥匙打开全部箱子的概率是多少。”

这还是去年写的文章，说第二天给答案，结果转眼过了一年……

其实这题用小学知识大概就能做出来。假设有 n 个箱子，砸开其中 m 个之后能用钥匙打开其它所有箱子的概率为 p(n, m)。我们先看最简单的，只有一个箱子的情况，砸开它就相当于打开了全部的箱子。那么显然有 p(1, 1) = 1。

类似地，两个箱子都砸开，三个箱子都砸开，打开全部箱子的概率都是 1。显然对于任意 n 个箱子，我们都有 p(n, n) = 1。

接下来再考虑 n 个箱子留其中一个箱子不砸开的情况。如果这个箱子里的钥匙恰好是打开自己的，那么这个箱子就不能被打开了，这种情况的概率是 1/n。剩下的 (n-1)/n 的概率，打开这个箱子的钥匙在其它被砸开的箱子里。因此我们有 p(n, n-1) = (n-1)/n。

那么我们再看看 n 个箱子留两个不砸开的情况。考虑其中一个没被砸开的箱子，如果它的钥匙就在自己里面，那么它肯定不能被打开；如果钥匙在另外一个没被砸开的箱子里面，那么要打开这个箱子，必须先打开另一个箱子。因此我们可以把这两个箱子看成一个，这样相当于只剩下 n-1 个箱子，那么问题就转化成 n-1 个箱子砸开了 n-2 个，我们根据刚才的结论知道这个问题的结果是 (n-2)/(n-1)；如果它的钥匙不在这两个没砸开的箱子里面，那么就在剩下的已被砸开的箱子里，这时这个箱子一定能被打开。那么问题依旧可以转化成 n-1 个箱子砸开了 n-2 个。这两种情况出现的总概率是 (n-1)/n，因此我们可以计算出总的概率是 p(n, n-2) = (n-2)/(n-1) * (n-1)/n = (n-2)/n。

用类似的方法，我们可以使用数学归纳法来证明 p(n, m) = m/n。

首先，我们有 p(n, n) = 1。

假设 p(n, m) = m/n，那么对于 n+1 个箱子砸开 m 个的情况，我们先考虑其中一个没被砸开的箱子，这时有三种情况：

1. 它的钥匙就在自己这个箱子里面。此时这个箱子永远无法被打开；
2. 它的钥匙在其它没被砸开的箱子里。这时我们可以把装它的钥匙的箱子与它想象成一个箱子。那么问题将被转化成 n 个箱子砸开 m 个。
3. 它的钥匙在已经被砸开的箱子里。那么可以用它的钥匙打开它，问题依旧转化成了 n 个箱子砸开 m 个。

2、3 两种情况出现的概率之和为 n/(n+1)，因此我们有 p(n+1, m) = p(n, m) * n/(n+1) = m/(n+1)

综上，我们可以得出结论：n 个箱子，砸开其中的 m 个，里面的钥匙恰好能打开全部箱子的概率就是 m/n 。

下面我们再加大点难度。如果不是每个箱子里恰好有一把钥匙，而是每把钥匙可以随机挑一个箱子装进去，也就是有的箱子里可能有多把钥匙，有的箱子里一把都没有。这时砸开其中几个箱子，恰好能打开全部箱子的概率是多少呢？