600 个人站一排，每次随机杀掉一个奇数位的人，几号最安全？ 第1页

修正之后的结论：存活回合数期望最大的应该是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]的黄金分割点上。