## Wednesday, May 12, 2010

### Solution: Passengers Boarding Airplane

Credit goes to Ed Kao, Vallent Lee and Laurence Tai for helping with the second solution.

Original problem: http://dharmath.blogspot.com/2009/10/passengers-boarding-airplane.html

2009 passengers are waiting in a line to board an airplane with 2009 seats. Each passenger has a boarding pass that has his/her seat number on it. The first passenger, however, was oblivious and chose a random seat to sit on.

For each subsequent passenger, he/she will try to sit on his/her assigned seat first. If that seat is taken by someone else, he/she will choose a random empty seat to sit on.

What is the probability that the last passenger would sit on his assigned seat?

Answer: $\frac{1}{2}$

First Solution

We generalize the problem to $n$ passengers boarding an airplane with $n$ seats.

The probability that the first passenger sits in his seat is $1/n$. We will prove by induction that the probability that the $k$-th ($k > 1$) passenger sits in his seat is $\frac{n-k+1}{n-k+2}$

For $k=2$, it's obvious that the second passenger has probability $\frac{n-1}{n}$ of finding his seat unoccupied. As long as the first passenger chooses something other than his seat, he will find his seat unoccupied and sits there correctly.

For $k>2$, consider the time when $k$-th passenger is about to board. If he finds his seat unoccupied, he will sit there. The only way that he does NOT sit on his correct seat is if it's already occupied by a previous passenger. We will divide this into two cases, depending on who sits at his seat.

Case 1: Passenger $k-1$ sits there. The only way this could happen is if passenger $k-1$ finds her seat occupied by someone else, and then she chooses to sit at passenger $k$'s seat. The probability of passenger $k-1$ finds her seat occupied by someone else is $1-\frac{n-(k-1)+1}{n-(k-1)+2} = \frac{1}{n-k+3}$.
At that point, there are $k-2$ occupied seats total and there are $n-k+2$ empty seats on the plane. The probability that she chooses to sit at this particular seat is $\frac{1}{n-k+2}$

Case 2: Passenger $i (i < k-1)$ sits there (at passenger $k$'s seat). Now we consider the moment where passenger $i$ was about to board. Passenger $k$'s seat was open.

If passenger $k-1$'s seat had been occupied by someone else before $i$, then passenger $i$'s seat would have been open, and passenger $i$ must have sit there correctly.

In order for passenger $i$ to NOT sit on his seat, both passenger $k$ and $k-1$'s seat are both open. That means, the probability that passenger $i$ sits at passenger $k$'s seat is the same as the probability that passenger $i$ sits at passenger $k-1$'s seat, since both choices are equally likely and they're always made with both choices available.

Thus the probability from case 2 is $\frac{1}{n-k+3}$

The total probability that passenger $k$ does not sit at his correct seat is:
$$\frac{1}{n-k+3} \frac{1}{n-k+2} + \frac{1}{n-k+3} = \frac{1}{n-k+2}$$
so the probability that he sits at his seat is:
$$1 - \frac{1}{n-k+2} = \frac{n-k+1}{n-k+2}$$
which completes the inductive step.

From this formula, it's clear that the probability passenger $n$ sits on his correct seat is $\frac{1}{2}$

Second Solution
We make the following observations:

1. In the beginning, both seat #1 and #2009 are both empty.
2. The moment someone chooses to sit on either seat (that is, the moment they stop being both empty), there is no more choices to be made for the rest of the boarding process. The rest of the passengers must thus sit deterministically from that point on.

Indeed, when passenger $k$ sits on seat #2009, then seat $k+1, ..., 2008$ would be empty and the subsequent passengers don't have to choose at all. Passenger #2009 has a random "choice" of 1 seat.
If passenger $k$ sits on seat #1, then the remaining vacant seats match the unboarded passengers perfectly and everyone can sit in their correct seat save for those who've already boarded.

That means, for every event that someone illegitimately sits on seat #2009, that passenger had an equally likely choice of seat #1, and vice versa. The moment this symmetry is broken, there would be no more choices to be made for the rest of the boarding process.

3. When passenger #2009 is about to board, there is only one empty seat. That empty seat is either seat #1 or seat #2009. If there is another seat $k ( 1 < k < 2009)$ empty, then one might ask: why didn't passenger $k$ sit there? A contradiction.

From the observations above, we define two events:
A: an event that passenger #2009 sits at seat #1
B: an event that passenger #2009 sits at seat #2009

These two events are mutually exclusive, and are the only two possibilities. Furthermore, they have equal probability since the moment one event becomes impossible, there is no more choices to be made by the rest of the passengers.

So the probability that passenger #2009 sits at his correct seat is $\frac{1}{2}$