国王与囚徒

某监狱里有100个囚犯，有一天国王对囚犯说：“明天我将和你们玩一个游戏，你们将轮流被带到一个房间里，房间里有100个按1到100编号的盒子，每个盒子里都有一张卡片，每张卡片上分别写着你们中一个人的名字，因为你们的名字都不一样，所以每张卡片的名字都不相同。你们每人可以打开50个盒子，但是不能移动任何一个盒子或者卡片，所有的盒子和卡片都会保持初始状态不变。假如某人在打开第50个盒子时或者之前找到自己的名字，那么他将被带到另一个隔离的地方，所有盒子都会重新合上，下一个犯人将被带到房间里继续进行游戏。如果你们所有人都找到自己的名字，游戏就算你们赢，你们所有人都将获释；但是假如有人找不到的话，那么游戏到此为止，你们将按照原来的刑期呆在监狱里。当然，在整个过程中你们不能做任何形式的暗号。但是你们有一个晚上商量对策。”假如所有囚犯都随机打开50个盒子的话，那么他们成功的机会就是1/2^100，机会约等于0。请问你能想出一个提高他们成功机会的策略吗？
当然囚徒不能挪动纸条盒子等，每次操作完都会将盒子移动到标准状态。

怎么算阶乘？

In [67]: def f(n):
   ....:     return reduce(lambda x,y: x*y, range(1,n+1))
   ....:

In [68]: f(4)
Out[68]: 24

介绍scipy 中的阶乘和排列组合函数 http://docs.scipy.org/doc/scipy/reference/misc.html#scipy.misc.comb

In [60]: import scipy.misc as sc
In [61]: f=sc.factorial

In [64]: f(4)
Out[64]: array(24.0)

In [65]: f(5)
Out[65]: array(120.0)

计算倒数和

def f2(n):
   return reduce(lambda x,y: x + 1.0 / y, range(1,n+1))

或者
f2 = lambda n: sum(1/float(x) for x in range(1, n+1))

首先把1-100这100个数字随机分配给100个囚犯，编号为i的囚犯进房间后先打开第i个盒子，假如里面是第i1个犯人的名，那么接着去打开第i1个盒子；假如第i1个盒子里是第i2个犯人的名字，那么去开第i2个盒子，直到找到自己的名字或者打开50个盒子。这样可以保证无论人数多少，成功的机会总是大于1 - ln2

不失一般化，先设有n个囚犯(n是偶数)。1-n这n个整数的每一种排列相对于原有顺序都可以分解成若干个循环，比如设有1234四个整数,2314这个排列可以表示成(123)和(4)两个循环，，2143可以表示成(12)和(34)两个循环。假如把卡片上的名字对应的编号看成是1-n的一种排列，那么同样可以分解成若干个循环，于是上述的方法相当于第i个犯人遍历整数i所在的循环，策略成功相当于该排列不存在一个长度大于n/2的循环。

现在来分析一个随机排列存在一个长度为k(k>n/2)的循环的概率。从n个数字里选k个循环里的数字共有C(n,k)种方法，每一种方法循环里的数字共有(k-1)!种排列方法，循环外的数字有(n-k)!种排列方法，所有的情况共有n!种，于是概率是 C(n,k)*(k-1)!*(n-k)!/n!=1/k。于是排列存在一个长度大于n/2的循环的概率p是p = 1/(n/2+1) + 1/(n/2+2) + 1/(n/2+3) + … + 1/n

上述p的值小于1/x在[n/2，n]上的定积分，有 p < ln n - ln n/2 = ln 2。于是成功的概率是 1-p，大于 1-ln 2，即无论人数多少，总能保证成功的机会大于 1-ln2，约30%。