Plane Boarding Puzzle: Will the Last Person Get Their Seat?

Introduction:

This is a classic problem for which you would usually have just a couple of minutes to solve.

Sometimes, in an interview, you might not have the necessary time to start from a particular case, but, this problem benefits a lot from this, by getting the right intuition for the answer. If you’ve never seen this before, this step is crucial.

So, let’s reduce the number of passengers to just two: the drunk and the unfortunate one that shares the plane with them. This situation is simple. The first passenger has a 50-50 chance of sitting in his chair. Thus, the probability of the last passenger finding his seat free is 50%.

If we abstract this probability to $p_i$ in the case of ‘i’ seats, we just proved that $p_2$ is $\dfrac{1}{2}$.

Let’s now consider the case where the plane has three seats. Denoting our passengers, in order, $a_1, a_2, a_3$, we have three (equally likely) possibilities:

• $a_1$ stumbles into his seat, leaving $a_2$ and $a_3$ free to board correctly;
• $a_1$ takes $a_3$‘s seat thus $a_3$ can’t sit in his assigned position;
• $a_1$ takes $a_2$‘s seat so $a_2$ will pick a random seat from the remaining two.

If we look closer now and re-label $a_1$‘s seat with $a_2$‘s name, $a_2$ is in the same position that the first passenger was in the situation with only two seats, leading us back to $p_2$.

Combining everything, we get that $p_3$ is $\frac{1}{2}$ as well.

Solutions:

First Method

The obvious follow-up is to prove the statement $p_n = \dfrac{1}{2}$ for any n greater than or equal to two via Complete Induction.

Start by assuming that $p_2, p_3 \dots p_k$ are all equal $\dfrac{1}{2}$. Looking at the ‘k+1’ seats case we have the following equally likely cases:

• $a_1$ sits in his seat, so everyone boards correctly with probability 1, including the last passenger
• $a_1$ sits in $a_2$‘s seat, so $a_2$ picks randomly, and by putting $a_2$‘s name on $a_1$‘s seat, we are in the case with k passengers, so, the last one will sit in his assigned place with probability $p_k$.
• $a_1$ sits in $a_3$‘s seat, sparing $a_2$ of the inconvenience, but passing it to $a_3$, who picks randomly, and, as before, leaving us in the case with $k-1$ passengers, so, the last one will sit in his assigned place with probability $p_{k-1}$.

We go down the list of passengers, with the second to last being the case when $a_1$ sits in $a_k$‘s seat, letting $a_2, a_3 \dots a_{k-1}$ to board in their assigned places, and forcing $a_k$ to pick randomly; This results in the final probability on this branch to be $p_2$.

And the last case is the one where $a_1$ sits in the last passenger’s place, making sure that $a_{k+1}$ sits in his rightful position with probability 0.

Averaging over all the equally likely cases, we get that $p_{k+1}$ is $\dfrac{1}{2}$ as well. Using the principle of mathematical induction, we can conclude that our sentence is true for any value of $n$, hence, the probability that the last passenger will fly in his own seat is $\dfrac{1}{2}$.

Second Method

As expected, using induction is not the only solution to this problem. You can also use solely logic to get the same result if you find the re-interpretation that makes the most sense to you. The insight that helped me understand this problem is the following:

Whenever someone finds their seat taken, they kick that person out, letting them choose a random seat.

This actually has no effect on the outcome for the last passenger. Let’s see how things play out in the original case and in this alternative way of handling a drunk passenger.

If we consider that the seats below are ordered in the same way as the passengers boarding we have the following outcomes:

• $a_1$ sits in a random seat, and after him, $a_2$ and $a_3$ occupy their places when $a_4$ boards and finds that $a_1$ is in his seat, he has 3 places to randomly choose from $a_5$, having his seat also occupied, has 2 seats to select from, and the last person in the queue will take the remaining seat, which, in this case, is his rightful one.

Now, let’s look at the same situation if the misplaced passenger is evicted from the seat. When $a_4$ evicts $a_1$, $a_1$ will have to make the same choice that a4 made in the previous case. The same is true for when $a_5$ boards the plane, hence, there is no change in where $a_6$ will sit between the two cases.

In this rephrasing, the first passenger keeps getting moved around and having to choose a new random seat. By the time everyone else has boarded, they have been forced by elimination either into their correct seat or into the last passenger’s seat.

At each step, the crucial two seats look the same to the first passenger, ie empty. So we are certain that the first passenger will choose one with the same probability as the other. Hence, the last passenger will get in his seat with a 50% chance.

Simulation:

We apply a direct approach to get our desired results, using just two external libraries:

• random - We use random’s choice function for seat selection
• collections - We use the Counter function for checking our results

We simulate a million boardings. For each, we look at each passenger consecutively, and, either seat him in if his place is available or randomly select one of the free ones. We store the last available seat for each iteration in an array.

import collections
 import random
 
 #vector for storing simulation results
 results = []
 
 #passenger counter
 n = 100
 
 #run the simulations
 for sim in range(int(1e6)):
     free_seats = set(range(1,n+1))

     for i in range(1,n):
         if (i==1) or (i not in free_seats):
             free_seats -= {(random.choice(list(free_seats)))}
         else:
             free_seats -= {i}
        
     results.append(list(free_seats))

 #check the results
 collections.Counter(results)