100位乘客排队登上一架满员的客机，但第一位乘客弄丢了登机牌，于是随便挑了一个座位坐下。此后每位乘客，如果自己的座位还空着，就坐自己的座位；否则就在剩下的空座位里随便挑一个。问：最后一位登机的乘客发现自己的座位还空着的概率是多少？
把座位按“本该坐它的人”编号：第\(i\)位乘客的座位就是\(i\)号座。
答案：\(\frac{1}{2}\)。 下面先看小规模的情形，再给出对任意人数都成立的论证。
2位乘客。 第一位等概率地坐1号座或2号座：坐1号座则最后一位有座，坐2号座则最后一位只能坐1号座。概率为\(\frac{1}{2}\)。
3位乘客。 第一位等概率地选1、2、3号座：
- 坐1号座（概率\(\frac{1}{3}\)）：人人都能坐自己的座位，成功；
- 坐3号座（概率\(\frac{1}{3}\)）：第二位坐2号座，第三位只能坐1号座，失败；
- 坐2号座（概率\(\frac{1}{3}\)）：第二位发现自己的座位被占，在1号座与3号座之间等概率挑一个——挑1号座则第三位有座，挑3号座则失败。
所以
\[ \frac{1}{3}+\frac{1}{3}\cdot\frac{1}{2}=\frac{1}{2}.\]
两个小情形都得到\(\frac{1}{2}\)，这提示答案或许与人数无关。要证明它，先看清一个结构上的事实。
考虑第\(i\)位乘客，这里\(1<i<n\)。他登机时只有两种可能：
- \(i\)号座已经被人占了：那它此后一直有人坐；
- \(i\)号座还空着：那他就坐上去。
无论哪种情况，第\(i\)位乘客登机之后，\(i\)号座都已被占。座位只会越坐越满，所以第\(n\)位乘客登机时，\(i\)号座一定是满的。
于是留到最后一位的座位只可能是1号座或\(n\)号座：其余\(n-2\)个座位都已被占，而此刻恰好只剩一个空位。结局因此只有两种——坐上自己的\(n\)号座（成功），或被迫坐1号座（失败）。
最后一步：那个仅剩的空位是\(n\)号座还是1号座，机会相等吗？
先注意，只要还有人需要随机选座，1号座与\(n\)号座就都还空着：
- 1号座若被占，要么是第一位乘客随机坐下的，要么是某次随机选座选中了它；无论哪种，此后人人都能坐自己的座位，不会再有随机选座；
- \(n\)号座属于最后一位乘客，只有随机选座的人才会坐它；它一旦被占，后面的人也都能坐自己的座位，同样不会再有随机选座。
而每次随机选座，都是从当时所有空座位里等概率挑一个。设当时有\(m\)个空座，则1号座与\(n\)号座被选中的概率都是\(\frac{1}{m}\)，处处相同。所以这两个座位在整个过程中受到完全相同的对待，“谁先被选中”纯属对称，各占一半：
- 1号座先被选中 → 此后人人有座，\(n\)号座留给了最后一位，成功；
- \(n\)号座先被选中 → 最后一位的座位没了，失败。
于是
\[ \Pr[\text{最后一位坐到自己座位}]=\frac{1}{2}.\]
也可以换个说法：最后恰好有一个座位空着，而1号座与\(n\)号座地位对称，所以“空着的是\(n\)号座”与“空着的是1号座”可能性相同，各为\(\frac{1}{2}\)。
- 整个论证没有用到\(n=100\)这个具体数字：只要\(n\ge2\)，答案都是\(\frac{1}{2}\)；\(n=1\)时当然是\(1\)。
- 也可以用递推核对：设\(f(n)\)为\(n\)位乘客时的成功概率。第一位乘客若坐1号座则成功，若坐\(n\)号座则失败；若坐第\(k\)位乘客的座位（\(2\le k\le n-1\)），第\(k\)位面对的就是“\(n-k+1\)位乘客、第一位丢了登机牌”的同一问题。于是\(f(n)=\frac{1}{n}\left(1+\sum_{m=2}^{n-1}f(m)\right)\)，由\(f(2)=\frac{1}{2}\)归纳即得\(f(n)=\frac{1}{2}\)。