这是一道非常有趣的概率题（LeetCode 1227），表面上看很复杂，但答案却出奇地简单优雅。

1. 问题设定

有 $n$ 位乘客即将登机，飞机正好有 $n$ 个座位。第一位乘客的票丢了，他随机选了一个座位坐下。

剩下的乘客按以下规则就座：

• 如果自己的座位还空着，就坐到自己的座位上
• 如果自己的座位被占用了，就随机选择其他空座位

问题：第 $n$ 位乘客坐到自己座位的概率是多少？

2. 从小规模情况入手

2.1 n = 1

只有一位乘客和一个座位。第一位乘客就是最后一位，他随机选择…其实就是唯一的座位。

答案：$P(1) = 1$

2.2 n = 2

第一位乘客有两种选择：

• 选择座位 1（概率 1/2）：第二位乘客坐自己的座位 2
• 选择座位 2（概率 1/2）：第二位乘客被迫坐座位 1

答案：$P(2) = \frac{1}{2}$

2.3 n = 3

第一位乘客有三种选择：

如果第一位选了座位 2，第二位面临的情况：

• 选座位 1（概率 1/2）：第三位成功
• 选座位 3（概率 1/2）：第三位失败

所以：

答案：$P(3) = \frac{1}{2}$

3. 模式识别

看起来答案总是 $\frac{1}{2}$！让我们尝试一般性证明。

4. 关键洞察

4.1 核心观察

考虑第一位乘客的选择：

• 选择座位 1（概率 $\frac{1}{n}$）：所有人都能坐自己的座位，第 $n$ 位成功
• 选择座位 $n$（概率 $\frac{1}{n}$）：第 $n$ 位注定失败
• 选择座位 $k$（$1 < k < n$，概率 $\frac{1}{n}$）：第 $k$ 位发现自己的座位被占

4.2 递归结构

当第一位选了座位 $k$（$1 < k < n$）时：

• 第 2 到 $k-1$ 位乘客都坐自己的座位（不受影响）
• 第 $k$ 位乘客发现座位被占，成为新的"疯子"

关键洞察：第 $k$ 位乘客面临的问题，与原问题完全等价！

只是规模从 $n$ 变成了 $n-k+1$，而两个"关键座位"（座位 1 和座位 $n$）仍然存在。

4.3 对称性

无论过程多么复杂，最终必定有人坐座位 1 或座位 $n$。

• 如果座位 1 先被坐：第 $n$ 位成功
• 如果座位 $n$ 先被坐：第 $n$ 位失败

由于整个过程的对称性，这两个事件的概率相等！

答案：$P(n) = \frac{1}{2}$，对所有 $n \geq 2$

5. 数学归纳法证明

归纳假设：$P(k) = \frac{1}{2}$ 对所有 $k < n$ 成立。

归纳步骤：

第一位乘客的选择：

由归纳假设，$P(n-k+1) = \frac{1}{2}$：

6. 代码实现

1
2
3
4
5
6
7
8

def nthPersonGetsNthSeat(n: int) -> float:
    """
    第 n 位乘客坐到自己座位的概率
    
    对 n = 1，概率为 1
    对 n >= 2，概率恒为 0.5
    """
    return 1.0 if n == 1 else 0.5

7. 拓展思考

7.1 如果问题变成"第 k 位乘客坐到自己座位的概率"？

答案仍然是 $\frac{1}{2}$（对 $k \geq 2$）。

7.2 为什么这么简单？

这个问题的美妙之处在于：尽管过程看起来很随机、很复杂，但最终只取决于两个关键座位（1 和 $n$）哪个先被占。而由于对称性，这两个事件等概率。

8. 小结

核心洞察：

1. 座位 1 和座位 $n$ 的对称性
2. 中间过程不影响最终结果
3. 问题具有递归结构

这道题提醒我们：面对复杂问题，寻找不变量和对称性往往能带来意外的简化。

相关题目：LeetCode 1227. Airplane Seat Assignment Probability