概率与数学面试题

问题建模

有 $N$ 名乘客和 $N$ 个一一对应的座位，按 $1,2,\ldots,N$ 到达：

• 第 1 人均匀随机选择一个座位；
• 第 $i$ 人若 $i$ 号座位空着就坐下，否则在剩余空位中均匀随机选择；
• 问第 $N$ 人最后坐到 $N$ 号座位的概率。

当 $N=1$ 时概率为 1；以下讨论 $N\ge 2$。

错位链只由两个终止座位决定

如果第 1 人坐到 1 号，所有后续乘客都坐自己的座位，第 $N$ 人成功；如果第 1 人坐到 $N$ 号，第 $N$ 人必然失败。

若第 1 人坐到中间的 $k$ 号座位，则第 2 到第 $k-1$ 人都正常就座。第 $k$ 人到达时自己的座位被占，他会在：

$$ \{1,k+1,k+2,\ldots,N\} $$

中随机选择。若又选中一个中间座位，被迫随机选择的人继续向后传递，形成一条错位链。

这条链只会以两种方式终止：

• 某人选中 1 号座位：此后所有人恢复正常，第 $N$ 人坐到自己的座位；
• 某人选中 $N$ 号座位：第 $N$ 人的座位被占，最终失败。

对称性证明

在错位链终止之前，1 号和 $N$ 号始终都在空位集合中。设某一步还有 $m$ 个可选空位，那么当前随机乘客：

$$ P(\text{选中 1 号}\mid\text{当前状态})=\frac1m $$

$$ P(\text{选中 N 号}\mid\text{当前状态})=\frac1m $$

选中其他中间座位只会把随机选择权传给下一位被占座者；新状态中 1 号和 $N$ 号仍然对称。因为有限个座位会不断被占用，过程最终必然命中两者之一。两个终止事件概率相等、总和为 1，因此：

$$ P(\text{最后一人坐到自己的座位})=\frac12 $$

递推证明

令 $p_N$ 表示 $N$ 人时最后一人成功的概率。按第 1 人第一次选择的位置分情况：

• 选 1 号：概率 $1/N$，条件成功率为 1；
• 选 $N$ 号：概率 $1/N$，条件成功率为 0；
• 选中间 $k$ 号：概率 $1/N$，之后剩下 $N-k+1$ 人和同样数量的相关空位，化为规模 $N-k+1$ 的同类问题。

所以：

$$ p_N=\frac1N+\frac1N\sum_{k=2}^{N-1}p_{N-k+1} =\frac{1+\sum_{j=2}^{N-1}p_j}{N} $$

基础情形为 $p_2=1/2$。假设 $p_2,\ldots,p_{N-1}$ 都等于 $1/2$，则：

$$ p_N=\frac{1+(N-2)\times\frac12}{N} =\frac{N/2}{N}=\frac12 $$

因此对所有 $N\ge2$，$p_N=1/2$。

为什么中间分支仍是同类问题

第 1 人占据 $k$ 号后，第 $k$ 人开始随机选择，相关空位是 $\{1,k+1,\ldots,N\}$。把 1 号座位视为第 $k$ 人在缩小问题中的“安全座位”，把第 $k$ 人视为新的随机乘客：

• 他会在所有相关空位中均匀随机选择；
• 后面的乘客仍然优先选择自己的座位；
• 原来的第 $N$ 人仍是最后一人；
• 选中安全座位则错位链终止，选中最后一人的座位则失败。

因此这不是形式上的类比，而是选择规则与成功事件完全保持不变的状态压缩。

高频追问