老杨 3:01 PM
动脑筋，中级，有一百个罪犯，他们的编号分别是1，2，3，…，100。监狱长有一个大柜子有100个抽屉编号也是1到100，他把1到100这100个数随机的放到这一百个抽屉里，每个抽屉放一个。罪犯们按编号一个一个的轮流到大柜子前来，每人可以打开50个抽屉，看能不能找到自己的编号，然后关上打开的抽屉。如果每个罪犯都找到了自己的编号，那么所有的罪犯都被释放。如果有一个没找到自己的编号，所有的罪犯都被处死。罪犯们在开始前可以商量，开始后则不准有任何的信息交流。你能不能设计一个策略提高罪犯们的成功几率，这个几率是多少？
https://en.m.wikipedia.org/wiki/100_prisoners_problem
先看人数少一点的情形，8个人，每人4次机会，假设有如下号码分布，最后都在规定次数内，找到了各自的号码：
如果换成下面的号码分布，很不幸，他们失败了，没能在4步以内找到自己的号码。
但如果允许他们找更多次，他们一样有机会找到各自的号码。
这里有一个神奇的地方，就是：任何一个犯人，只要从他自己号码的抽屉开始找，顺藤摸瓜，最终一定能找到自己的号码。
差别在于，几步能找到？是不是在监狱官方规定的步数之内？
但为什么这些数字会有这么奇特的性质？这主要是由这两组数的特性决定的。这两组数的形成可以看成这样一个过程，先顺序排好一个序列，保存。然后把同样长度的序列，做一次随机排序，再把两组数并列放在一起。这样的结果就是，有些单元，或许两个一样，但绝大多数单元两个数不一样。
如果两个数一样，就表示该号码的犯人一下子在自己号码的抽屉里找到了自己的号码，这几乎是天上掉馅饼（上面例2中的6）。
一般情况下，两个数不一样。那么用一个数作为下一个单元的索引，这样一直走下去，最终必然会出现最初的那个数，当然，步数可短（如一步，也就是相互索引，如上面例1中的3和6），也可以很长，但最终一定会出现，哪怕是走一个包括所有数的循环（例如，假如把两个顺序序列，移动一个位置，那就是走完整个循环，才找到自己的号码）。
有了这一点知识，我们就知道，只要这样的链条的最大长度小于等于监狱官方规定的步数，那么所有的犯人都一定能找到自己的号码。只要有一条链条的长度大于监狱官方规定的步数，那么这个链条上的人就都不能在规定的步数之内找到自己的号码（因为自己号码的抽屉里是另一个人号码，而要等到自己的号码再出现，一定要走完整个链条）。
有了上面的理解，那么原来的问题就转化成，100个随机数，产生这种链条的最大长度小于等于50的概率是多大？这个可以看网上的解答（https://en.m.wikipedia.org/wiki/100_prisoners_problem），大约31%。这跟1/2的100次方比起来，简直是天文数字了。
可见，学好数学是多么的重要！！！
再想象一下极端的情况。如果监狱官方允许每个犯人打开99个抽屉，如果按照传统的随机瞎摸的方法，成功的概率是：（99/100）^100 = 大约36.6%
而按照这里的聪明办法，成功的概率是99%。
