题目描述：

现有100名囚犯，编号1～100；100个位于密闭房间中的不透明容器，编号1~100；以及一百张分别写有数字1~100的纸条

现将100张纸条随机放入100个容器中

然后，让100名囚犯分别进入房间中，每名囚犯可以打开50个容器，寻找与自己编号相同的纸条，开完50个容器后，必须将所有东西放回原位，且不得与其他囚犯有交谈。但在这之前，囚犯们可以商量对策。若所有囚犯都找到了与自己编号相同的纸条，这这100名囚犯可以全部无罪释放，但若有一人没找到自己编号的纸条，则所有人必须继续服刑

那么，囚犯们应该选择怎么样的策略，才能使得无罪释放就几率最大？

策略

首先，很容易想到全随机选择，那么对于单个囚犯来说，找到自己的纸条的概念均为，那么100名囚犯都找到自己纸条的概率自然是

这是个什么概念呢？

据估计，地球上沙粒的数量在左右，也就是说，使用这个策略获胜的可能性，是让你从地球上随机挑出一颗沙粒，挑到指定的那一粒沙粒的概率的不足亿分之一，可见这必然不是最佳策略

那么我们应该使用怎样的策略呢？

我们知道：对任意一个容器而言，其中有一张纸条，不管纸条编号是否与容器相同，其纸条必定指向箱子，像这样，容器中有纸条，纸条指向箱子，形成一个循环，直到容器中有纸条，此时循环结束

我们称这样的循环为“环”，记作

那么对于囚犯，其只需要从容器开始寻找，对所在的环进行遍历后，必定能在容器中找到纸条，考虑到囚犯只能打开至多50的容器，则所在的环的长度必须小于51，即

那么，这个策略成功的概念，就是100个纸条和100个容器随机组合，形成的若干个环中，最长环的长度小于等于50的概率

求出概率

在下文中，我们记最长环的长度为

要得到的概率，直接算肯定不好算，因为长度小于等于50的最长环有时不止一个

但是，的情况肯定只有一个最长环，我们可以计算，那么：

考虑

选出n个数，不妨令这个环的结构如下：

容易知道：

第一个数字有n-1种选择，第二个数字有n-2种选择，以此类推，第的数字有种可能，而第n个数字只有一种可能，才能保证成环

那么这个环就有种排法

考虑剩下的容器，用同样的方法可以算出有有种可能

故长度为n的环有

种

所以：

故长度最长的环长度为n的概率为

这个式子的值约为0.688

则成功几率为1-0.688=0.312

可见，使用这种策略可以使成功的几率大大提高

优势

更有趣的是，这种策略所带来的优势随着人数的上升而增加

则获胜几率为：

故成功几率稳定在

而这比的值要大的多

注：

本专栏是基于视频BV17W4y1S7WR的基础上撰写，对部分原视频讲的不清楚的地方进行了补充，主要是最长环概率处，感兴趣的也可以去看这个视频

另外，没意外这就是我暑假的最后一更了，过几天就要去新学校报道了，上了高中不能常更新，可能只有长假才会更新了，不好意思啦~