600 个人站一排，每次随机杀掉一个奇数位的人，几号最安全？
在最前面，为了简单，我们用一个简记符号，其中$ \lceil x\rceil $表示上取整：
$$ \tau_{x} = \lceil \frac{x}{2} \rceil $$
现在我们假设有 $n$ 个人，第$k$ 个人存活到最后的概率为$p(n,k)$。考虑第一个杀死的人的位置，很容易我们就能得到递推式子：
$$ p(n, k) = \frac{\tau_{k-1}}{\tau_n} \times p(n-1,k-1) + \frac{\tau_n-\tau_k}{\tau_n} \times p(n-1, k)$$
到这里之后可以用计算机程序快速算出数值结果。但这里有个奇妙的地方在于，它的符号解也特别简单：
$$ p(n, k) = \frac{\tau_{k-1}}{\tau_{n-1}\tau_n} $$
更直观的看，每个人存活的概率为 0, 1, 1, 2, 2, 3, 3, 这样一直下去，最后再标准化（使得概率总和为 1 ）。结果非常优美。
很容易验证上面的结果和递推式。但如果不是提前知道答案，直接从上面的递推式子很难猜到。我们可以换一种方法，注意到下面这个事实：前面的$m$个人的存活（相对）概率分布和后面有多少人没有关系，这样我们只用把最后一个人的存活概率算出来，然后再往前推，就可以获得所有的存活概率。
最后一个人存活概率$p(n) = p(n, n)$有一个简单递推式：
$$ p(2n) = p(2n-1)$$
$$p(2n+1) = \frac{n}{n+1} p(2n)$$
结合$p(1) = p(2) = 1 $，很简单就可以得出：
$$ p(n) = \frac{1}{\tau_n}$$
然后我们算倒数第二个人：
$$ p(n,n-1)=(1-p(n))\times p(n-1) = \frac{\tau_{n-2}}{\tau_{n-1}\tau_n}$$
然后有一个特别好的递归式：
$$ \tau_0 + \tau_2 + \cdots + \tau_{n-1} = \tau_{n-1} \tau_n$$
$$ \tau_{k-1}\tau_k + \tau_k + \tau_{k+1} + \cdots + \tau_{n-1} = \tau_{n-1} \tau_n$$
用上面式子类似地往前推，可以得出：
$$\begin{equation}\begin{split} p(n,k)&=(1-p(n,k+1)-p(n,k+2)-\cdots-p(n,n))\times p(k,k) \\ &= \frac{\tau_{n-1} \tau_n-\tau_k-\tau_{k+1}-\cdots-\tau_{n-1}}{\tau_{n-1} \tau_n} \times\frac{1}{\tau_k} \\ &= \frac{\tau_{k-1}\tau_k}{\tau_{n-1} \tau_n}\times\frac{1}{\tau_k } \\ &= \frac{\tau_{k-1}}{\tau_{n-1}\tau_n} \end{split} \end{equation}$$
Q. E. D.
