监狱求生

Posted by WildCow on April 8, 2018

昨天在写大连海事大学校赛的时候
发现一题
原型在 gls 知乎专栏里看到过
当时看到就觉得很有意思
趁这个机会
在 gls 的同意下把那个专栏的内容转载过来
感谢 gls @好地方bug
祝 gls 和 清欢 百年好合

一个有趣的问题

有100个犯人被关在监狱里,邪恶的监狱长构思了一个处决犯人的计划。监狱长准备了100个盒子,每个盒子里面装有一个犯人的名字。他将这100个盒子排成一排,放在一个房间里面。一开始,所有犯人都在房间的外面,然后依次进入房间,每位进入房间的犯人可以开启50个盒子,然后关上。在所有犯人都进入房间后,如果有哪个犯人没有看到自己的名字,那所有的犯人都会被处以极刑。

请问如何制定一个策略,使得犯人们的存活概率最大

注意:在邪恶监狱长的计划开始后,每位犯人都不能从其他犯人那里得到任何信息(比如前面的人有没有看到自己的名字)。

不采取任何策略

首先考虑犯人们不采取任何策略,这样以来,每位犯人看到自己的名字的概率将会是 1/2 ,所以总的存活概率就是 $(1/2)^{100}$ ,显然这基本等于不可能了。。

一个简单的改进

不妨按照进入房间的顺寻将犯人编号,从1到100。虽然每个犯人不能从前面的犯人那里得到任何信息,但是自己要活下来,必须先假设其他人都看到了对应的名字,所以容易想到一个简单的改进:

  • 奇数编号的人都开前50个盒子
  • 偶数编号的人都开后50个盒子

让我们来考虑一下这时候,前两个人存活的概率,是不是比 1/4 更小。令事件 A 表示两个人都活下来,事件$ B_1 $是第一个人看到自己的名字,事件$ B_2 $是第二个人看到自己的名字。显然, A 应当是$ B_1 $和$ B_2 $联合事件。容易知道$ B_1 $和$ B_2 $并不独立,这是因为,如果第一个人在前50个盒子里面看到了自己的名字,那么第二个人就不可能看到第一个人的名字,换言之,在假设第一个人能看到自己名字的情况下,第二个人相当于在99个盒子里面抽50个盒子。那么我们有:



两两一组,整体活下来的概率就是$ (\frac{25}{99})^{50} $,比不采取任何策略要好很多了,但是还是依然处于不可能的阶段。

炫酷吊炸天的改进

现在来一个质的飞跃的改进。使得概率可以达到 1/3 左右!!

还是像之前的策略一样,按照进入房间的顺序给所有人编号,从 1 到 n ,然后给所有盒子编号,从 1 到 n 。我们采取如下策略:

  • 第 i 个人开第 i 个盒子,如果看到里面的自己的名字,则结束
  • 第 i 个人开第 i 个盒子,如果没看到自己的名字,看到第 j 号人的名字,则去开第 j 个盒子,这样直到看到自己的名字。 这样做有什么好处呢?不妨设$ w_1,w_2,\cdots,w_k $为$ w_1 $号人访问的盒子序列,他最终在$ w_k $里面看到了自己的名字。那么$ w_1,w_2,\cdots,w_k $便构成了一个长度为 k 的环。所以,如果一个人没有看到自己的名字,那么他的名字一定在一个长度大于50的环里面

所以问题就变成了,有多少种排列,其中最大的环的长度不超过50

不妨来计算反面,有多少种排列,包含一个长度大于 50 的环,更一般的,我们希望得到,有多少种排列,包含一个长度为 r 的环,r > 50。

先选 r 个出来,计算这 r 个能排列出多少种环,最后把剩下的 100-r 个随便排列即可(由于 r>50 ,所以剩下的不可能构成长度为 r 的环)。

  • 选 r 个出来:$ \binom{100}{r} $
  • 这 r 个元素能构成的环的个数:$ (r-1)! $,这是由于,对于这 r 个数字来说,第一个数字有 r-1 个选择位置的方法,既是选择后继的方法,对于第二个数字来说,有 r-2 个选择后继的方法,……,对于第 r 个数字来说,只有一种选择后继的方法。称起来便是$ (r-1)! $
  • 剩下的元素随便排列:$ (100-r)! $

所以有$ \sum_{r=51}^{100}\binom{100}{r}(r-1)!(100-r)!=\sum_{r=51}^{100}\frac{100!}{r} $种排列,其中最大的环的长度超过 50。

所以我们的概率便出来啦:

$P=1-\sum_{r=51}^{100}\frac{1}{r} \approx0.31 $

于是犯人们便能愉快的赌命了。。。。。