600个人站一排,每次随机杀掉一个奇数位的人,几号最安全?

修正之后的结论:存活回合数期望最大的应该是2,但最可能成为最后一个存活的人的是600。

我们来研究M个人杀N次的情况下,每个位置被杀的概率。

可以用递推法计算。首先2个人杀一次的情况下,2一定是最好的,,。M个人杀一次的情况下,偶数被杀概率为0,奇数被杀概率相等:,

考虑M+1个人杀N+1次的情况,则很容易得到:

我们定性分析一下这个式子,无论奇数还是偶数,都从(M,N)的情况中,继承自己和前一项的“阵亡”概率,同时补上自己是奇数(有被杀概率)或者是偶数(无被杀概率)的修正值。k越小,前一项加权越小,后一项加权越大。奇数项有额外的加成。这样,k比较小的情况下,奇数项和偶数项的差异越来越大;而k越大,由于前后两项平均、甚至前项比例超过后项的效果,奇数项和偶数项的差距变得越来越小。

迭代下去的结果大致是一个上下波动然后衰减的样式:1的被杀概率最大,2最小,3又变大但小于1,4又变小但大于2,依次类推。M和N都比较大的时候,靠后位置的奇数位置、偶数位置差异变得很小,因为它们经常相互转换。而1永远是奇数;2只有很小的概率会转换成1。N越大,存活概率的绝对值都变小,但存活概率与前后位置的关系变得更大,2的相对安全优势也越明显。如果考虑最后一个存活的人的比例的话,N很大的情况下,2的优势会很明显。

====================================================================

事实证明全凭臆想是不好的……这里忽略了一件事,一开始在2,和最后几轮在2,意义是完全不同的。一开始奇数多,每个奇数被杀概率比较小,而最后几轮被杀概率严重提高,而一开始在2的,很容易就滑到1去了。还是老老实实算一下递推式……

存活概率:

杀至最后一人的存活概率。这也太直了吧!

但其实并不是完美直线,而是奇数偶数一组跳变的,1的存活概率是0,(2,3)的存活概率几乎一样,(4,5)的存活概率几乎一样,依次类推,所以最后存活概率最大的是600,它存活的概率几乎就是1/300。

实际上似乎有

我们代回去检验一下:

这提示我们也许应该用存活概率来表示递推式,改写一下,用Q(k; M, N)来表示存活概率:

的确可以去掉那个常数项,改写成齐次的递推式。

在N不为M-1的时候,得到的结果跟之前的分析基本一致(Q(600,300)):

(0实际上是1)

当N增大的时候,这个图也有变化,下图是Q(600,500):

最安全的已经不是2了,而是向后移动,但并没有移动到非常远的地方。

进一步增大的时候(Q(600,550)):

中间大部分地方都变平了,但是注意看那个尾巴,会下降一些,原因不明,但应该不是计算误差,因为随着N增大,这个尾巴变得越来越明显,以至于到599的时候,尾巴变成了整条直线。

更有趣的是这个尾巴的朝向跟N的奇偶性密切相关(Q(600,551)):

尾巴变成向上了。

N接近于599的时候:

Q(600,595)

波动越来越不明显,而尾巴越来越明显。

Q(600,596)

Q(600,597)

Q(600,598)

变成了一个这样的奇怪曲线……

然后599就突变成了直线。只能说,数学真是太奇妙了。

附Python代码:

def fr ( a , b = None ):

if b is None :

return a

else :

return float ( a ) / float ( b )

# Uncomment the following line to use fractions

# from fractions import Fraction as fr

def cal_p ( m , n ):

P = [ fr ( 0 )] * ( m – n + 1 )

for M in range ( m – n + 1 , m + 1 ):

P2 = [ 0 ] * ( M + 1 )

half = ( M + 1 ) // 2

P . append ( fr ( 0 ))

for i in range ( 1 , M + 1 ):

if i % 2 == 0 :

P2 [ i ] = fr ( i // 2 , half ) * P [ i – 1 ] + fr ( half – i // 2 , half ) * P [ i ]

else :

P2 [ i ] = fr ( 1 , half ) + fr ( i // 2 , half ) * P [ i – 1 ] + fr ( half – i // 2 – 1 , half ) * P [ i ]

P = P2

return P

import matplotlib.pyplot as plt

def plot_q ( M , N ):

P = cal_p ( M , N )

q = [ 1.0 – p for p in P [ 1 :]]

plt . figure ()

plt . plot ( q )

plt . show ()

如果考虑存活回合数的期望值的话,由于N很大的时候存活概率本身就比较小,最后的确应该是2的平均存活回合数比较有优势吧。

解释一下当N比较大的时候,为什么随着N的奇偶性变化,最后一段的概率忽大忽小呢?

因为我们的M = 600是个偶数,当杀奇数人的时候,最后一轮排在最后一个位置的人不会被杀,而杀偶数人时,最后这一轮排在最后一个位置的人可能被杀,而就是这一点点差别导致了差异;杀奇数人时,最后一段很容易成为最后一个人,所以存活概率变大了,在杀599人的时候,甚至这是唯一的存活可能性;杀偶数人时,反而是成为倒数第二个人比较划算,所以最后一小段反而概率下降了。

猜一猜,598那个曲线的极值点在什么位置?

在[0,600]的黄金分割点上。

来源:知乎 http://www.zhihu.com

作者:灵剑

【知乎日报】千万用户的选择,做朋友圈里的新鲜事分享大牛。

点击下载

此问题还有 111 个回答,查看全部。

延伸阅读:

如何用简单易懂的例子解释隐马尔可夫模型?

在进行线性回归时,为什么最小二乘法是最优方法?

Advertisements

Tags: