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.
An airplane has 50 seats, and its 50 passengers have their own assigned seats. The first person to enter the plane ignores their seat assignment and instead picks a seat uniformly at random. Each subsequent person to enter the plane takes their assigned seat, if available, and otherwise chooses a seat uniformly at random. What's the probability that the last passenger gets to sit in their assigned seat?
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 their 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 they choose 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 they choose. If $S=1,$ then all subsequent passengers will take their assigned seats, including passenger $50,$ so $P(E \mid S=1)=1.$ If they choose seat $50,$ then passenger $50$ can never take their own seat, so $P(E \mid S=50)=0.$ Suppose they choose 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 theirs 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 they take. 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 their 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 their assigned seat is $1/2.$ $\Box$