Drunk Passenger (100 Airplane Seats): Puzzle and Step-by-Step Solution
Probability
Medium
Reported at Jane Street, Citadel, Hudson River Trading, Two Sigma
The puzzle
One hundred passengers board a plane with 100 assigned seats, one at a time. The first passenger has lost their boarding pass and sits in a seat chosen uniformly at random. Every later passenger sits in their own seat if it is free, and otherwise picks a free seat uniformly at random. What is the probability that the last passenger sits in their own seat?
Short answer: Exactly 1/2, whatever the number of seats (as long as there are at least two).
Step 1: Try two and three seats first
With two seats, the first passenger takes seat 1 or seat 2 with equal chance. If seat 1, the second passenger gets their own seat; if seat 2, they do not. The answer is 1/2.
With three seats, the first passenger takes seat 1 (probability 1/3, and everyone is fine), seat 3 (probability 1/3, and the last passenger loses) or seat 2 (probability 1/3). In the last case passenger 2 picks between seats 1 and 3 at random, so the last passenger wins half the time. Total: 1/3 + 1/3 × 1/2 = 1/2. The answer is 1/2 again, which suggests a structural reason.
Step 2: The symmetry argument
Watch only two seats: seat 1 (the lost passenger's) and seat 100 (the last passenger's). Whenever someone is displaced and chooses at random, either they pick seat 1, they pick seat 100, or they pick some other seat, which just displaces one more passenger and passes the problem on.
The moment anyone picks seat 1, every remaining passenger, including the last, finds their own seat free, and the last passenger wins. The moment anyone picks seat 100, the last passenger loses. At every random choice, seat 1 and seat 100 are equally likely to be picked, because the choice is uniform over free seats and both are free until one of them is taken.
So the game ends with seat 1 taken first or seat 100 taken first, with equal probability. The last passenger gets their own seat with probability exactly 1/2.
Step 3: Checking the argument with a recursion
Let p(n) be the answer with n seats. The first passenger picks seat 1 with probability 1/n (win), seat n with probability 1/n (lose), or seat k in between, which turns passenger k into a new random chooser in an equivalent problem with n - k + 1 seats. So p(n) = 1/n + (1/n) × the sum of p(n - k + 1) for k from 2 to n - 1. If every smaller p equals 1/2, this gives 1/n + (n - 2)/(2n) = 1/2, so by induction p(n) = 1/2 for every n from 2 up.
A related follow-up: the probability that passenger k, for k between 2 and 100, finds their seat taken is 1/(102 - k). It is worth knowing that the last passenger is the only one with even odds.
Why interviewers ask it
Interviewers want you to compute small cases, spot the 1/2, and then find the symmetry between seat 1 and seat 100. A recursion that confirms it is a bonus, not a substitute.
Knowing the proof is half of it. Work Drunk Passenger (100 Airplane Seats) interactively, then take it under a clock with the rest of the Outcry simulators.