Passenger Plane Puzzle

In this post I will attempt to show that sitting down and having a nice cup of tea is the best approach to solving any new mathematical problem.  So, here's a problem:

A plane has 100 seats and 100 passengers each with an allocated seat number.  The first passenger to get on the plane is blind and chooses a seat at random.  Each subsequent passenger to board chooses their own seat if still available, or a seat at random if not.  What is the probability that the 100th passenger gets their allocated seat?

This is more subtle than it seems at first.  The last passenger could get their own seat because the blind passenger chooses the correct seat, or because the 2nd passenger chooses the blind person's seat, or because the first 87 passengers occupy the first 87 seats.  In fact there's a huge number of ways in which it could happen.

Knuckleheaded Compsci solution

Suppose we've forgotten to have a cup of tea.  Then we might just dive in and start modelling it, like this:

 

def run_once():
    N = 100
    seat = random.randint(0,N-1)
    avail = set(range(N)) - set([seat])
    for passenger in range(1,N):
        seat = passenger if passenger in avail else random.choice(list(avail))
        avail = avail - set([seat])
    return passenger == seat

 

Then, running this 1000 times we might see it returns True 495 times and False 505 times.  A properly knuckleheaded compsci might then turn round and say: it's one half init.  Which is probably True but

1. It might be $\frac{1}{2} + e^{-100}$, or anything else close to a half.
2. Even if it is $\frac{1}{2}$, we have gained no insight as to why!

Knuckleheaded mathmo solution

If you give it to a mathmo who has forgotten to have a cup of tea they might take this approach:

If there were just 2 passengers the probability would obviously be
$$
P_2 = \frac{1}{2}
$$
If there were 3 passengers then there's a one third likelihood that the blind passenger takes the 1st seat. There's also a one third probability that the blind passenger takes the 2nd seat which would need to be mulitplied by one half (the probability that the 2nd passenger takes the 1st seat), so
$$
P_3 = \frac{1}{3} + \frac{1}{3}\cdot \frac{1}{2} = \frac{1}{2}
$$
Hmm. This suggests a proof by induction. Suppose
$$
P_2 = P_3 = ... = P_n = \frac{1}{2}
$$

Then, $P_{n+1}$ is the sum of the following probabilities

• The blind passenger chooses the 1st seat
• The blind passenger chooses the 2nd seat, and in the virtual plane of $n$ seats in which the 2nd passenger is blind, the last passenger gets their own seat
• The blind passenger chooses the 3rd seat, and in the virtual plane of $n-1$ seats in which the 3rd passenger is blind, the last passenger gets their own seat
• ...
• The blind passenger chooses the $n$th seat, and in the virtual plane of 2 seats in which the $n$th passenger is blind, the last passenger gets their own seat

So,

$$
\begin{align}
P_{n+1} &= \frac{1}{n+1} + \frac{P_n}{n+1} + ... + \frac{P_2}{n+1} \\
&= \frac{1}{n+1}\left( 1 + \frac{1}{2} (n-1)\right) \\
&= \frac{1}{n+1}\left(\frac{n+1}{2}\right) \\
&= \frac{1}{2}
\end{align}
$$

This is better.  We know the answer is exactly 1/2.  But in a sense we're no better off because we still have no insight why.

Cup of tea and a sit down solution

Have a cup of tea and a sit down, and you'll start thinking more laterally.  When the last passenger gets on the plane what seats could still be available?  It has to be either the last passenger's or the blind passenger's, since any other would have been taken when the rightful passenger boarded.  But none of the previous 99 passengers discriminated between these two seats, making them equally likely to be the last one left.  Insight!