Taking Seats on a Plane

Question

This is a neat little problem that I was discussing today with my lab group out at lunch. Not particularly difficult but interesting implications nonetheless

Imagine there are a 100 people in line to board a plane that seats 100. The first person in line, Alice, realizes she lost her boarding pass, so when she boards she decides to take a random seat instead. Every person that boards the plane after her will either take their "proper" seat, or if that seat is taken, a random seat instead.

Question: What is the probability that the last person that boards will end up in their proper seat?

Moreover, and this is the part I'm still pondering about. Can you think of a physical system that would follow this combinatorial statistics? Maybe a spin wave function in a crystal etc...

Answer 1

This is a classic puzzle!

The answer is that the probability that the last person ends in up in their 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 person 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.

Answer 2

This analysis is correct, but not complete enough to convince me. For example, why is the fate of the last person settled as soon as the first person's seat chosen? Why will any other seat but the first person's or the last person's be taken by the time the last person boards?

I had to fill in the holes for myself this way...

The last person's fate is decided as soon as anybody chooses the first person's seat (nobody is now in a wrong seat, so everybody else gets their assigned seat, including the last person) or the last person's seat (the last person now won't get their correct seat). Any other choice at any stage doesn't change the probabilities at all.

Rephrasing... at each stage, either the matter gets settled and there is a 50/50 chance it gets settled each way for the last person's seat, or the agony is just postponed. The matter can thus be settled at any stage, and the probabilities at that stage are the only ones that matter -- and they are 50/50 no matter what stage. Thus, the overall probability is 50/50.

Answer 3

I don't really have the intuition for this, but I know the formal proof. This is equivalent to showing that the probability that in a permutation of $[n]$ chosen uniformly at random, two elements chosen uniformly at random are in the same cycle is $1/2$. By symmetry, it's enough to show that the probability that $1$ and $2$ are in the same cycle is $1/2$.

There are many ways to show this fact. For example: the probability that $1$ is in a cycle of length $k$ is $1/n$, for $1 \le k \le n$. This is true because the number of possible $k$-cycles containing $1$ is ${n-1 \choose k-1} (k-1)! = (n-1)!/(n-k)!$, and the number of ways to complete a permutation once a $k$-cycle is chosen is $(n-k)!$. So there are $(n-1)!$ permutations of $[n]$ in which $1$ is in a $k$-cycle. Now the probability that $2$ is in the same cycle as $1$, given that $1$ is in a $k$-cycle, is $(k-1)/(n-1)$. So the probability that $2$ is in the same cycle as $1$ is $$ \sum_{k=1}^n {k-1 \over n-1} {1 \over n} = {1 \over n(n-1)} \sum_{k=1}^n (k-1) = {1 \over n(n-1)} {n(n-1)\over 2} = 1/2. $$

Alternatively, the Chinese restaurant process with $\alpha = 0, \theta = 1$ generates a uniform random permutation of $[n]$ at the $n$th step; $2$ is paired with $1$ at the second step with probability $1/2$. This is a bit more elegant but requires some understanding of the CRP.

Answer 4

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 (Alice, who lost her boarding pass) keeps getting evicted (and choosing a new random seat) until, by the time everyone else has boarded, she has been forced by a process of elimination into her 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, Alice is either in her own seat or in the last boarder's seat, which have both looked exactly the same (i.e. empty) to her up to now, so there is no way poor Alice could be more likely to choose one than the other.

Answer 5

Let $P(n)$ denote the probability of the last passenger getting his seat if we begin with $n$ passengers.

Consider the simple case for just $2$ seats:

$P(2) = \frac12$ (first boarder picks his own seat with 1/2 probability)

For $n$ seats: (i) With $\frac1n$ probability, the passenger picks the seat of the first passenger, the n'th seat from the end (in which case the last passenger would definitely get his seat). (ii) With 1/n probability, the current passenger picks the seat of the last passenger, first seat from the end (and now, the last passenger can definitely not get his own seat). (iii) Otherwise, the passenger picks some other seat (say #i from the end) among the n-2 remaining seats (with probability 1/n), continuing the dilemma. The problem now reduces to the initial problem with i seats.

Therefore, $$ P(n) = \frac1n \times 1 + \frac1n \times 0 + \frac1n\sum_{i=2}^{n-1} P(i) $$ or $$ nP(n) = 1 + \sum_{i=2}^{n-1} P(i).$$ So $$nP(n)-(n-1)P(n-1)=P(n-1)\Longleftrightarrow P(n)=P(n-1),$$ and $P(n)=P(2) = \frac12, \,\forall n \ge 2$.

Answer 6

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.

Answer 7

Here is a simple proof. For $k\ge 2$, let $p_k$ be the probability that the $k$-th person's seat is taken when he/she tries to sit.

We consider the disjoint events that person $j$ takes up this particular seat, for $1\le j \le n$. In order for that to happen, $j$'s seat has to be taken, and then $j$ is left with $n-j+1$ random choices of which $j$ must take $k$'s seat. We can write: $$p_{k}={1\over n}+p_2{1\over n-1}+p_3{1\over n-2}\dots+p_{k-1}{1\over n-k}.$$

Thus, $p_2={1\over n}$, $p_3={1\over n}+{1\over n(n-1)}={1\over n-1}$. In general, $p_k={1\over (n-k+2)}$.

Answer 8

A recursive solution: Once a passenger who has been displaced from their assigned seat sits in the seat assigned to passenger $1$, no more passengers will be displaced. But if the displaced passenger takes some other seat, a passenger still standing in line will become displaced

Let the plane have $N$ seats and let $r_n$, $1\le n\le N-1$, be the probability that with $n$ passengers standing in line none of the standing passengers is displaced from their assigned seat. We have $r_{N-1}=\frac{1}{N}$ because that is the probability the first passenger happens to choose their own seat. If $n$ passengers are standing in line and somebody in line is displaced—it will always be exactly one passenger—the probability that the displaced passenger is at the head of the line is, by symmetry among the standing passengers, $\frac{1}{n}$. And if the displaced passenger is at the head of the line, the probability that they take the seat assigned to passenger $1$ is also $\frac{1}{n}$. It follows that $$ r_{n-1}=r_n+\frac{1-r_n}{n^2}. $$ By induction, we find that $r_n=\frac{1}{n+1}$ and hence $r_1=\frac{1}{2}$.

Another recursive solution: This expands on Shashank's answer, emphasizing a key point that caused me some confusion at first.

When a non-displaced passenger gets to the head of the line, they simply take their assigned seat, but when a displaced passenger gets to the head of the line, they choose uniformly at random from the set $$ \{\text{passenger 1's seat}\}\cup\{\text{seats assigned to passengers standing behind them in line}\}. $$ Although technically passenger $1$ is not displaced, they follow the same procedure as the displaced passengers do, so we lump them in with that group. As a consequence, if passenger $k$ is displaced, then when that passenger gets to the head of the line, the situation is just like the original problem, but for a plane of $N-k+1$ passengers.

Define $p_n$ to be the probability that, in the setup described, the last passenger to board an $n$-seat airplane gets their assigned seat. Then for $n\ge2$, $$ p_n=\frac{1}{n}\cdot1+\left[\frac{1}{n}\sum_{k=2}^{n-1}p_{n-k+1}\right]+\frac{1}{n}\cdot 0. $$ Each term in this expression corresponds to a seat choice of passenger $1$: if the choice is seat $1$, passenger $n$ gets their assigned seat with probability $1$; if it's seat $k$, for $2\le k\le n-1$, then passengers $2$ through $k-1$ take their assigned seats and, when passenger $k$ comes to choose a seat, it is like the original problem but with $n-k+1$ seats; if the choice is seat $n$, then passenger $n$ gets their assigned seat with probability $0$.

Multiplying by $n$ and reversing the order of summation gives $$ np_n=1+\sum_{k=2}^{n-1}p_k. $$ Subtracting this from the same recurrence with $n$ replaced by $n+1$ gives $$ (n+1)p_{n+1}-np_n=p_n, $$ for $n\ge2$. Hence $p_2=p_3=p_4=\ldots$. One easily sees $p_2=\frac{1}{2}$.

The stumbling block for me was in seeing the similarity between passenger $1$ and the displaced passengers. Passenger $1$ chooses randomly among the available seats, which include their assigned seat, and I got hung up on the possibility that passenger $1$ might get their own seat, which can't happen for other displaced passengers. That, however, is not the correct parallel to draw. The right parallel is that both passenger $1$ and the displaced passengers can get passenger $1$'s seat, which ends the cycle of displacement.

Several other answers on this page, like (this, this, and this) —jump straight to an even simpler recurrence. The recurrence does hold and can be derived from this one, but haven't been able to understand how to get that recurrence directly. This issue was raised by Hans on this page in a number of his comments. If I stumble upon any insight that might help other readers with this point, I will add it here.

Solution using conditional probability: we have seen that if seat $1$ is chosen before the last passenger is seated, then that passenger sits in their assigned seat; if seat $N$ is chosen before the last passenger is seated, then the last passenger is displaced and must take seat $1$. Let $E_k$ be the event that the $k$th passenger to be seated is the first to take one of seats $1$ and $N$. Then $$ \Pr(\text{$N$ gets their assigned seat})=\sum_{k=1}^{N-1}\Pr(\text{$k$ sits in $1$}\mid E_k)\Pr(E_k)=\frac{1}{2}\sum_{k=1}^{N-1}\Pr(E_k)=\frac{1}{2}. $$ Diagrammatically, this calculation is shown below. The probability that $N$ gets their assigned seat is the sum of the probabilities that each of passengers $1$ through $N-1$ takes seat $1$.

Solution using a bijection between cycles: (This completes a final, needed step in hunter's answer.) The seating process results in a permutation of the passengers, and this permutation always consists of a single cycle containing passenger $1$ followed by displaced passengers, an ascending order. So for $N=100$ the cycle $(1,46,53,75,88)$ represents the situation where passenger $1$ displaces passenger $46$, $46$ displaces $53$, $53$ displaces $75$, $75$ displaces $88$, and $88$ sits in passenger $1$'s seat. Passengers $89$ and up, and passenger $100$ in particular, will sit in their assigned seats. The cycle $(1,46,53,75,88,100)$ represents a similar situation, except that passenger $88$ displaces passenger $100$. Passengers $89$ through $99$ will sit in their assigned seats, and passenger $100$ will have only one choice of seat: passenger $1$'s seat.

The probability of occurrence of these two cycles is the same: $$ \frac{1}{100}\frac{1}{55}\frac{1}{48}\frac{1}{26}\frac{1}{13}. $$ In general, when displaced passenger $k$ chooses a seat, they choose uniformly at random from $101-k$ possible seats. Once passenger $88$ has chosen either seat $1$ or seat $100$ (each of which happens with probability $\frac{1}{13}$), the seating of the remaining passengers standing in line is determined. Now every cycle that does not contain $100$ is paired in this way with an equally probable cycle that does contain $100$. Hence passenger $100$ sits in their assigned seat with probability $\frac{1}{2}$.

Answer 9

There are two sub problems. First to show that person $n$ has only two choices. Second to show that the probability is $\frac{1}{2}$. The first doesn't immediately imply the second.

sub-problem 1: When person $n$ boards, then he will not find seat $n-1$ empty. Why? If $n-1$ was empty when $n$ boards, it was also empty when $n-1$ boarded and he ($n-1$) would have taken seat $n-1$.

Similarly, when person $n$ boards, then he will not find seat $n-2$ empty. Why? If $n-2$ was empty when $n$ boards, it was also empty when $n-1$ and $n-2$ boarded and he ($n-2$) would have taken seat $n-2$.

Hence when person $n$ boards, the only seats that can possibly be available are either seat $1$ or seat $n$.

sub-problem 2: It is easier with example. The possible options for $n=4$ are:

1234

2134
3124
4123
4132

4213
3214

4231

Notice the location of person $1$.
seat $1$: $2^0$
seat $2$: $2^2$
seat $3$: $2^1$
seat $4$: $2^0$

So when person $1$ is seated fixed in seat $2$, the problem of distributing the remaining persons $2,3,4$ will be the same as the original problem but with $3$ people (convince yourself) with $4$ being last half the time. And if person $1$ is fixed in seat $3$ (implies that person $2$ is seat $2$) this reduces to a problem with $n=2$ with person $4$ being last half the time.

By induction, if we assume number of ways for $n$ is $2^{n-1}$.

For $n+1$ people, we get total number by looking at location of person $1$:
seat $1$: $2^0$
seat $2$: $2^{n-1}$
seat $3$: $2^{n-2}$
seat $n+1$: $2^0$

with total being $2^n -1 +1 = 2^n$ and half the time last person is in last location.

Interestingly, other than person $1$, each person is in their assigned seat half the time.

Answer 10

I know I am late to this question but I came here as a result of a link from this closed question: 100 seats Quant problem

I believe this is simpler than the solutions I see. Imagine that we simulate a coin toss with a wheel with three outcomes: red, white and blue.

We let red be heads and white be tails. If we get a blue, we spin again. That's exactly what is happening in this problem.

If the first person, chooses his own seat then everyone else, including the last person, will get his own seat. If the first person chooses the last seat then the last person doesn't get his seat. Otherwise, the first person chooses another seat and the game continues.

Everyone gets their own seat up to the person that was chosen in the first round. Let's say the first person chose $47$, for example, Then seats $2$ through $46$ will have their rightful owners and person $47$ will have to choose. His choices are $1$, $100$ or something else. In each case, if $1$ is chosen then the last person gets his seat, if $100$ is chosen, he doesn't get his seat and if something else is chosen then the game continues.

In this sense, we are essentially spinning the wheel until we get either a $1$ or $100$ so the probability that the last person gets his seat is $\frac{1}{2}$.