Puzzle: Leon Lin sent me this great puzzle: 100 people are in line, boarding an airplane with 100 seats, one at a time. They are in no particular order. The first person has lost his boarding pass, so he sits in a random seat. The second person does the following:
Everyone else behind him does the same. What is the probability that the last person sits in his correct seat?
Hint: Consider a two-seat airplane, then grow it from there.
Answer: 50%
Solution: There are many ways to come up with this answer, but here’s one that makes sense to me. For ease of explanation we’ll say that I’m the first person to sit down and you’re the last. Also if you sit in your own seat then you “win”, otherwise you “lose”.
Let’s say that there are only two seats, yours and mine. If I sit in my own seat, you win. If I sit in your seat, you lose. So you have a 50% chance of winning.
Now let’s go back to 100 seats. The previous paragraph still holds true: you have a 50% chance of winning if we only consider your seat and mine. Now if I sit anywhere else, I’m just postponing the decision. Let’s say I sit in the seat of the person who’s 13th in line. Persons 2 through 12 will sit in their own seats, then when person 13 comes in he can either sit in my original seat (and you win) or yours (and you lose). Or of course he could sit anywhere else and postpone the decision again.
If this keeps going, then eventually there are only two seats left and person 99 is forced to choose either your seat or mine, again with 50% chance. There are only two seats that matter throughout the game: yours and mine. Any sitting in other seats is just postponing the decision of which of the two interesting seats gets sat in first. Note also that you’ll only ever end up in your seat or mine, no one else’s.
It’s a bit like flipping a coin, except that you can postpone flipping, but not indefinitely. What’s the chance of coming out heads? Well 50%, the postponement doesn’t change that.
Here’s a mathematical way to see it. Define \(f(n)\) to be the chance that the last person in an airplane of \(n\) seats will get his own seat. It can be defined recursively like this:
$$f(n) = {1 \over n} 1 + {n - 2 \over n} f(n - 1) + {1 \over n} 0$$
The first term is the chance that the first person will sit in his own seat (\(1 \over n\)) multiplied by the chance, then, that the last person will sit in his own (\(1\)). The last term is the chance that the first person will sit in the last person’s seat (\(1 \over n\)) multiplied by the chance, then, that the last person will get his own seat (\(0\)). The middle term counts every other seat. There are \(n - 2\) other seats, and there’s a \(1 \over n\) chance of each, and they all simplify to the \(f(n - 1)\) case. Also:
$$f(2) = 0.5$$
If you plug in \(0.5\) for the \(f(n - 1)\) term, you find that \(f(n) = 0.5\), so it’s true for any \(n > 1\).