启动蒙特卡洛动态验证系统

傻子坐飞机问题：打破直觉的 $\frac{1}{2}$

1. 登机牌消失的灾难

2. 陷入直觉的陷阱与数学推导

面对庞大且混乱的接力占座过程，我们的直觉往往会“死机”。很多人会下意识地认为答案是 $1/n$，因为随着前面的人乱坐，最后剩下的那个座位似乎充满了极大的随机性。

为了击破直觉的陷阱，我们可以通过严谨的数学推导（全概率公式与数学归纳法）来揭示这背后的真相。

第一步：建立数学模型

设 $P(n)$ 为有 $n$ 名乘客时，最后一名（第 $n$ 名）乘客坐到自己座位（第 $n$ 号座位）的概率。

当第一名“傻子”乘客登机时，他在 $n$ 个座位中随机盲选，面临三种情况：

• 他刚好坐到了 1 号座位（概率为 $1/n$）： 这意味着他没有占任何人的位置，后续的所有人（第 2 到第 $n$ 名）都会顺利对号入座。此时，第 $n$ 个人必定能坐对自己位置。
  这一项的概率贡献为：$\frac{1}{n} \times 1$
• 他直接坐到了 $n$ 号座位（概率为 $1/n$）： 这意味着他一上来就把最后一名乘客的位置给占了，第 $n$ 个人绝对不可能坐对自己位置。
  这一项的概率贡献为：$\frac{1}{n} \times 0$
• 他坐到了中间的某个座位 $k$ ，其中 $1 < k < n$（选择具体某个 $k$ 的概率为 $1/n$）：
  此时，第 2 到第 $k-1$ 名乘客都能对号入座。但是，当第 $k$ 名乘客登机时，他发现自己的位置被“傻子”占了！此时，飞机上还剩下 $n-k+1$ 个空座位（包括 1 号、第 $k+1$ 到第 $n$ 号）。
  由于自己的座位没了，第 $k$ 名乘客只能在这剩下的 $n-k+1$ 个座位中盲选。这相当于第 $k$ 名乘客变成了新的“傻子”，开启了一场规模缩小为 $n-k+1$ 人的子游戏。在这个子游戏中，最后一人坐对的概率是 $P(n-k+1)$。

第二步：列出递推公式

将上述三种情况结合起来，我们得到递推关系式：

$$P(n) = \frac{1}{n} \cdot 1 + \frac{1}{n} \cdot 0 + \sum_{k=2}^{n-1} \left( \frac{1}{n} \cdot P(n-k+1) \right)$$

提取公因式 $\frac{1}{n}$，化简得到：

$$P(n) = \frac{1}{n} \left( 1 + \sum_{k=2}^{n-1} P(n-k+1) \right)$$

第三步：使用数学归纳法证明

我们要证明：对于任意 $n \ge 2$，$P(n) = \frac{1}{2}$。

• 基础情况 ($n=2$)：
  2 个人 2 个座位。第一个人选 1 号（概率 1/2），第二个人坐对；第一个人选 2 号（概率 1/2），第二个人坐错。所以 $P(2) = 1/2$。成立。
• 归纳假设：
  假设对于所有小于 $n$ 的正整数 $x$（$2 \le x < n$），都有 $P(x) = \frac{1}{2}$。
• 归纳证明：
  将归纳假设代入我们刚刚推导出的 $P(n)$ 公式中。求和符号 $\sum_{k=2}^{n-1}$ 中一共有 $n-2$ 项，并且每一项 $P(n-k+1)$ 的值都是 $\frac{1}{2}$。
  $$P(n) = \frac{1}{n} \left( 1 + \sum_{k=2}^{n-1} \frac{1}{2} \right)$$ $$P(n) = \frac{1}{n} \left( 1 + (n-2) \cdot \frac{1}{2} \right)$$ $$P(n) = \frac{1}{n} \left( \frac{2}{2} + \frac{n-2}{2} \right)$$ $$P(n) = \frac{1}{n} \left( \frac{n}{2} \right) = \frac{1}{2}$$