Source

I got this problem from Rustan Leino, who got it from Rajeev Joshi, who Rustan thinks said he heard it from Jay Misra.

I solved it and wrote up my solution.

Problem

An airplane has 50 seats, and its 50 passengers have their own assigned seats. The first person to enter the plane ignores his seat assignment and instead picks a seat uniformly at random. Each subsequent person to enter the plane takes her assigned seat, if available, and otherwise chooses a seat uniformly at random. What's the probability that the last passenger gets to sit in her assigned seat?

Solution
Reveal

The probability is $1/2,$ by the following reasoning.

Number the passengers, and their respective seats, $1$ through $50$ using the order in which the passengers will enter the plane. Let $E$ be the event that the last passenger, passenger $50,$ gets to sit in her assigned seat, seat $50.$ We will show that $P(E) = 1/2.$ We start with the following useful lemma.

**Lemma.** Suppose that at some point, for some $n$ such that $2 \leq
n \leq 49,$ the first $n-1$ passengers have taken seats $2$ through $n$
(not necessarily in that order). In this case, $P(E) = 1/2.$

*Proof.* We will prove this statement by induction on $n.$ As our
base case, we use $n = 49.$ In this case, passenger $49$ has two options:
seat $1$ or seat $50.$ $E$ happens if and only if she chooses seat $1$,
so $P(E) = 1/2$ and this case is proved.

Now, for the inductive step, we prove it holds for $n=N$ assuming it holds for all $N < n \leq 49.$ In this case, seats $2$ through $N$ are taken, so passenger $N$ will have to choose randomly among seats $1, N+1, N+2, \ldots, 50.$ Let $S$ be the seat she chooses. If $S=1,$ then all subsequent passengers will take their assigned seats, including passenger $50,$ so $P(E \mid S=1)=1.$ If she chooses seat $50,$ then passenger $50$ can never take her own seat, so $P(E \mid S=50)=0.$ Suppose she chooses any other seat $n$ such that $N+1 \leq n \leq 49.$ Then, passengers $N+1$ through $n-1$ will all get to take their own seats, after which passenger $n$ will try to take hers but find that all seats $2$ through $n$ are taken. So, by the inductive hypothesis $E$ will happen with probability $1/2.$ In other words, $P(E \mid N+1 \leq S \leq 49) = 1/2.$ Adding up all the conditional probabilities of $E$, we see that \[ \begin{eqnarray*} P(E) & = & P(E \mid S=1) P(S=1) + P(E \mid S=50) P(S=50) + P(E \mid N+1 \leq S \leq 49)P(N+1 \leq S \leq 49) \\ & = & (1)\frac{1}{51-N} + (0)\frac{1}{51-N} + (1/2)\frac{49-N}{51-N} \\ & = & \frac{(51-N)/2}{51-N} \\ & = & 1/2. \end{eqnarray*} \] So, the induction is proved.

Now we can consider what happens when the first passenger takes a random seat. Let $T$ be the seat he takes. If $T=1,$ then all passengers will sit in their assigned seats, including passenger $50.$ So, $P(E \mid T=1) = 1.$ If $T=50,$ then passenger $50$ won't be able to take her seat, so $P(E \mid T=50) = 0.$ If $2 \leq T \leq 49,$ then passengers $2$ through $T-1$ will be able to take their assigned seats but passenger $T$ will find seats $2$ through $T$ taken. So, by the lemma, $E$ will occur with probability $1/2.$ So, $P(E \mid 2 \leq T \leq 49) = 1/2.$ Adding up all the conditional probabilities of $E$, we see that \[ \begin{eqnarray*} P(E) & = & P(E \mid T=1) P(T=1) + P(E \mid T=50) P(T=50) + P(E \mid 2 \leq T \leq 49)P(2 \leq T \leq 49) \\ & = & (1)\frac{1}{50} + (0)\frac{1}{50} + (1/2)\frac{48}{50} \\ & = & 1/2. \end{eqnarray*} \] So, the probability that the last passenger sits in her assigned seat is $1/2.$ $\Box$