The Airplane Problem

Here’s a neat little problem I came across when solving some probability puzzles. It took me a couple of hours to realize the solution, and it took my younger brother around 30 minutes for a much more elegant solution. Both are detailed below.

Problem StatementPermalink

Imagine there are a $100$ people in line to board a plane that seats $100$. The first person in line realizes he lost his boarding pass so when he boards he decides to take a random seat instead. Every person that boards the plane after him will either take their “proper” seat, or if that seat is taken, a random seat instead. What is the probability that the last person that boards will end up in his/her proper seat.

SolutionPermalink

The answer can be arrived at by working backwards.

Refer to the $n^{th}$ person by $P_n$. Let $p_n$ denote the probability that $P_{100}$ gets their proper seat assuming $P_1$ occupies $P_n$’s seat. Now, consider the case where $P_1$ occupies $P_{n-1}$’s seat. Then there are two possibilites:

• $P_{n-1}$ occupies $P_1$’s seat
• $P_{n-1}$ occupies $P_k$’s seat, $\forall k \in [n, 100)$

In the first case, $P_{n} \rightarrow P_{100}$ will all occupy their corresponding “proper” seats. Further note that the second case is the same as if $P_1$ had occupied $P_k$’s seat, for which the probability that $P_{100}$ gets their seat is $p_k$. In both situations, the chances of $P_{n-1}$ picking any seat are $\frac{1}{100 - (n-1) + 1}$. Therefore,

Clearly, $p_n\vert_{n=100} = 0$. Using the relation derived above, we can calculate $p_{99}$ as $p_{99} = \frac{1}{2}\left(1 + 0\right) =\frac{1}{2}$. Similarly, $p_{98} =\frac{1}{3}\left(1 + \frac{1}{2} + 0\right) = \frac{1}{2}$. In fact, $p_k = \frac{1}{2}$ for all $k$ such that $1 \leq k < 100$. Lastly, note that each of these cases can occur with a probability of $\frac{1}{100}$, since $P_1$ can choose $P_k$’s seat randomly with a probability $\frac{1}{100}$. Therefore, the probability of $P_{100}$ getting their proper seat is

Elegant SolutionPermalink

The following solution might possibly blow your mind, and it is fitting that my brother came up with it. Let us say $P_1$ takes $P_k$’s place for some $k \in [1, 100)$. Then $P_2 \rightarrow P_{k-1}$ will take their proper seats. Further, $\exists$ a closed “chain” of seat occupancy, where $P_k$ can occupy someone else’s seat, who further can occupy a third’s seat. This closed “chain” will always end with someone occupying $P_1$’s seat.

For example, for some $n \in (k, 100)$, $P_k$ can occupy $P_n$’s seat, and $P_n$ can occupy $P_1$’s seat to form the chain, $P_1 \rightarrow P_k \rightarrow P_n \rightarrow P_1$. For $P_{100}$ to get their “proper” seat, they should be absent from this chain. Therefore,

Note that the no. of possible such “chains” given $N$ people is $2^N$ since each person can either be present or not be present in the chain.