醉酒乘客

Drunk Passenger

专题: Probability / 概率
难度: L4
来源: Brainstellar

题目详情

100 名乘客依次登机，每人持有一个指定座位（第 $n$ 个乘客的票对应座位 $n$ ）。

第 1 个乘客喝醉了，会在 100 个座位中等概率随机选一个坐下。

之后的乘客都清醒：若自己的座位空着就坐自己的；若被占了，就在剩余空座位中等概率随机选一个坐。

问：最后一位（第 100 个）乘客最终坐到自己座位（100 号座位）的概率是多少？

A line of 100 airline passengers is waiting to board a plane. They each hold a ticket to one of the 100 seats on that flight. For convenience, let's say that the $n^{\text{th}}$ passenger in line has a ticket for seat number 'n'. Being drunk, the first person in line picks a random seat (equally likely for each seat). All of the other passengers are sober, and will go to their assigned seats unless it is already occupied; If it is occupied, they will then find a free seat to sit in, at random. What is the probability that the last (100th) person to board the plane will sit in their own seat (#100)?

Hint

Can the last passenger arrive at any other seat than 1 or 100?

解析

答案是 $\frac{1}{2}$ 。

关键观察：最后一位乘客最终只可能坐到 1 号或 100 号座位。

在整个过程中，第一次“随机选座”的乘客会在候选集合 {1 号, 100 号, 其他未被打乱的座位} 中等概率选择。由对称性，1 号与 100 号谁先被占用的概率相同，因此最后一人坐到 100 号座位的概率为 $1/2$ 。

Original Explanation

1/2

Solution

Note that the last passenger can only take seat #1 or #100.

If any passenger takes seat #1, the cycle stops, and all the subsequent passengers take their own seats (including the last).
Otherwise, if the #100 seat is taken before #1, the cycle is paused, i.e., the subsequent passengers do take their own seats, but the last passenger would take seat #1.

Now, any passenger from 1st to 99th who is picking a random vacant seat will choose between #1, #100 or any other seat equally likely. Thus, by symmetry, #1 or #100, anyone will be taken first - with equal probability.

Hence the last person ends up in their own seat with a probability of 0.5

Follow-up Question

What's the probability that the second-last person sits on their seat?

Follow-up Answer

$2/3$ . The answer follows from the same logic of symmetry between the choice of seat #1, seat #100 and seat #99.

The probability that the $k^{\text{th}}$ person from the last will find their seat vacant is $k/(k+1)$ .

Script

Not convinced? Simulate using this Colab Script