One hundred passengers are lined up to board a full flight. The first passenger lost his boarding pass and decides to choose a seat randomly. Each subsequent passenger (responsible enough to not lose their boarding pass) will sit in his or her assigned seat if it is free and, otherwise, randomly choose a seat from those remaining. What is the probability that the last passenger will get to sit in his assigned seat?
A systematic solution by induction [1,2]
To gain insight that hopefully leads to solving the full problem, mathematicians usually study a reduced scenario that is easier to solve. Taking this approach, we consider two passengers boarding a two-passenger plane. In this case, the only way for the second (last) passenger to sit in his assigned seat is if the first passenger happens to choose his own seat. Since the first passenger chooses one of the two seats randomly, the probability that the second passenger gets his own seat is 1/2.
Let $p(n)$ be the probability that the $n$th passenger gets his or her assigned seat on an n passenger plane. We determined that $p(2)=\frac{1}{2}$.
Next, consider when there are three people boarding a three-passenger plane. If the first passenger takes his own seat, the second passenger's seat will be free for him or her to sit, and the third (last) passenger will get his own seat. However, if the first passenger takes the second passenger's seat, the second passenger must randomly choose between the first passenger and the third passenger's seat. The third passenger then gets the assigned seat only if the second passenger happens to choose the first passenger's seat, which has a probability of 1/2 since there are only two options and the choice is random. If the first passenger chooses the third passenger's seat, there is no hope that the third passenger will get his or her seat, of course. We have exhausted all ways of the last (3rd) passenger getting his or her seat.
$p(3)=$ 1/3 + (1/3) (1/2)
$p(3)=$ 1/3 + (1/3) (1/2)
Notice this fact that screams induction: when the first passenger chose the 2nd passenger's seat, the second passenger now plays the role of the first passenger in that when considering $p(2)$-- the 2nd passenger has two seats to randomly choose from, and one of them is the seat of the third, and last, passenger. So, we could write:
$p(3) = \frac{1}{3} + \frac{1}{3} p(2)$.
Now, for four passengers, consider all ways that the last passenger can occupy his own seat.
$p(4) =$ 1/4 + 1/4 p(3) + 1/4 p(2) = 1/4 + (1/4) (1/2) + (1/4) (1/2) = 1/2.
The first passenger takes his own seat.
The first passenger takes passenger #2's seat, and passenger #2 has three seats to randomly choose from-- one of which is passenger #4's seat. This is the $p(3)$ problem.
The first passenger takes passenger #3's seat, and passenger #3 has two seats to randomly choose from-- one of which is passenger #4's seat. This is the $p(2)$ problem.
Again, we get 1/2. We reduced the problem into the previous cases for $p(2)$ and $p(3)$, which we already know.
For finding $p(n)$ ($n>1$), the probability that the first passenger takes his own seat is $\frac{1}{n}$. If the first passenger takes the $K$th passenger's seat ($K>1$), passengers $2,3,4,...,K-1$ will get their seats, but passenger $K$ will be faced with the reduced problem of having $n - (K-1)$ seats to randomly choose from, one of which is the last passenger's seat-- this is the $p(n-K+1)$ problem! So, as above, we consider all possible seats that the first passenger can possibly choose (with a $\frac{1}{n}$ chance) and bring the $p(n-K+1)$ problems into play:
$p(n) = \frac{1}{n} + \displaystyle \sum_{K=2}^{n-1} \frac{1}{n} p(n-K+1) = \frac{1}{n} \left(1 + \displaystyle \sum_{K=2}^{n-1} p(n-K+1) \right).$
By the above recursion starting with $p(2)=\frac{1}{2}$, we can show that $p(n)=\frac{1}{n} \left(1+(n-2)\frac{1}{2} \right)=\frac{1}{2}$. For every $n$-- and this includes $n=100$ for this problem-- we have that the probability that the last passenger sits in his assigned seat is 1/2.
I expected it to be much less.
I expected it to be much less.
A more insightful solution: paraphrased from [3]
The trick is to consider just before the last passenger boards the plane, and one seat is left.
Claim: The last free seat is either the first or the last passenger's assigned seat.
proof by contradiction. Assume that the last seat belongs to passenger #$x$ that is not the first or last passenger. Since passenger $x$ boarded the plane before the last passenger, passenger $x$ did not sit in his or her assigned seat, violating the problem statement.
One seat is now left for the last passenger. The event that the last person's seat was taken is equivalent to the event that the first passenger's seat was taken before the last person's seat. This is because of the above claim: if the last passenger's seat is taken, then the last passenger must sit in the assigned seat of the first passenger. If the first passenger's seat is taken, then the last passenger sits in his own assigned seat. Since each time a passenger chooses a seat that is not assigned to them, the choice is random, there is no bias for a passenger to choose the first passenger's seat over the last. Thus, the probability of the last passenger sitting in his assigned seat is 1/2.
Claim: The last free seat is either the first or the last passenger's assigned seat.
proof by contradiction. Assume that the last seat belongs to passenger #$x$ that is not the first or last passenger. Since passenger $x$ boarded the plane before the last passenger, passenger $x$ did not sit in his or her assigned seat, violating the problem statement.
One seat is now left for the last passenger. The event that the last person's seat was taken is equivalent to the event that the first passenger's seat was taken before the last person's seat. This is because of the above claim: if the last passenger's seat is taken, then the last passenger must sit in the assigned seat of the first passenger. If the first passenger's seat is taken, then the last passenger sits in his own assigned seat. Since each time a passenger chooses a seat that is not assigned to them, the choice is random, there is no bias for a passenger to choose the first passenger's seat over the last. Thus, the probability of the last passenger sitting in his assigned seat is 1/2.
[2] Understanding Probability by Henk Tijms. This book is written in a colloquial style and has very interesting examples-- highly recommended.
[3] http://www.nd.edu/~dgalvin1/Probpuz/probpuz3.html
[3] http://www.nd.edu/~dgalvin1/Probpuz/probpuz3.html
