每次隨機殺掉一個奇數位的人後的存活概率問題
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.
「其他文章」