国王与囚徒
某监狱里有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%。 |
1717 次浏览 |
13次 |
|
捐助 |
|
|
|
|
|