Taking Seats on a Plane

Here is a rephrasing which simplifies the intuition of this nice puzzle.

Suppose whenever someone finds their seat taken, they politely evict the squatter and take their seat. In this case, the first passenger keeps getting evicted (and choosing a new random seat) until, by the time everyone else has boarded, he has been forced by a process of elimination into his correct seat.

This process is the same as the original process except for the identities of the people in the seats, so the probability of the last boarder finding their seat occupied is the same.

When the last boarder boards, the first boarder is either in his own seat or in the last boarder's seat, which have both looked exactly the same (i.e. empty) to the first boarder up to now, so there is no way the poor first boarder could be more likely to choose one than the other.

This is a classic puzzle!

The answer is that the probability that the last person ends in up in his proper seat is exactly $\frac{1}{2}$

The reasoning goes as follows:

First observe that the fate of the last person is determined the moment either the first or the last seat is selected! This is because the last person will either get the first seat or the last seat. Any other seat will necessarily be taken by the time the last guy gets to 'choose'.

Since at each choice step, the first or last is equally probable to be taken, the last person will get either the first or last with equal probability: $\frac{1}{2}$.

Sorry, no clue about a physical system.

Let's find the chance that any customer ends up in the wrong seat.

For $2\leq k\leq n$, customer $k$ will get bumped when he finds his seat occupied by someone with a smaller number, who was also bumped by someone with a smaller number, and so on back to customer $1$.

This process can be summarized by the diagram $$1\longrightarrow j_1\longrightarrow j_2\longrightarrow\cdots\longrightarrow j_m\longrightarrow k.$$
Here $j_1<j_2<\cdots <j_m$ is any (possibly empty) increasing sequence of integers strictly between $1$ and $k$. The probability of this sequence of events is $${1\over n}\times{1\over(n+1)-j_1}\times {1\over(n+1)-j_2}\times\cdots\times{1\over(n+1)-j_m}.$$

Thus, the probability that customer $k$ gets bumped is $$p(k)={1\over n}\sum\prod_{\ell=1}^m {1\over(n+1)-j_\ell}$$ where the sum is over all sets of $j$ values $1<j_1<j_2<\cdots <j_m<k$. That is, \begin{eqnarray*} p(k)&=&{1\over n}\sum_{J\subseteq\{2,\dots,k-1\}}\ \, \prod_{j\in J}{1\over (n+1)-j}\cr &=&{1\over n}\ \,\prod_{j=2}^{k-1} \left(1+{1\over (n+1)-j}\right)\cr &=&{1\over n}\ \,\prod_{j=2}^{k-1} {(n+2)-j\over (n+1)-j}\cr &=&{1\over n+2-k}. \end{eqnarray*}

In the case $k=n$, we get $p(n)=1/2$ as in the other solutions. Maybe there is an intuitive explanation of the general formula; I couldn't think of one.

---

Added reference: Finding your seat versus tossing a coin by Yared Nigussie, American Mathematical Monthly 121, June-July 2014, 545-546.