# Taking Seats on a Plane

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 realizes he lost his boarding pass so when he boards he decides to take a random seat instead. Every person that boards the plane after him 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 his/her 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...

• To make an analogy between this puzzle and a physical system, you would need to think of some system where particles or objects have "assigned locations" (separate from their actual location). This is not typically the case in physics, which usually concentrates only on how things actually are, and the dynamics of how things change. – Matt Feb 28 '15 at 11:45

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.

• This is a good intuitive way to think about it. A formal proof is too heavy for a over-a-cup-of-coffee discussion, this is just right. I'll give you the credit since nobody seems to want to take a shot at the physical application – crasic Sep 29 '10 at 8:23
• Could you please elaborate how the fate of the last person is determined the moment either the first or the last seat is selected? and how any other seat will necessarily be taken by the time the last guy gets to 'choose'.? – Mathgeek Jan 20 '17 at 19:50
• @Mathgeek: Suppose the last guy gets seat X, which is neither the first seat, nor the last seat. What seat did person numbered X take? – Aryabhata Jan 23 '17 at 23:26
• @Mathgeek: Yes, it will be 1. – Aryabhata Jan 25 '17 at 22:11
• This answer is good, but I think fails to make a fundamental insight: at any given time there is only one person who is yet to board and whose seat has been taken. This is because when someone boards either they sit in their seat or they take someone else's seat, but remove themselves from the queue. In both cases the net number of pre-taken seats doesn't change. – Stella Biderman Mar 30 '17 at 14:33

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 answer also gives an intuitive explanation for the nice result in Byron Schmuland's answer: When the $k$th passenger reaches the plane, there are $n-(k-1)$ empty seats. If the first passenger stands up, he will see that he is in an arbitrary one of $n-k+2$ seats, all of which have looked the same to him so far. So there is a $\frac{1}{n-k+2}$ chance that, when seated, he is occupying the $k$th passenger's seat. – Matt Aug 19 '14 at 2:22

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 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. 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.

• may i ask 2 questions, 1: how could I get $\sum_{J\subseteq\{2,\dots,k-1\}} \prod_{j\in J}{1\over (n+1)-j} = \prod_{j=2}^{k-1} \left(1+{1\over (n+1)-j}\right)$? 2. the bumping may not start from customer 1, it could start from anyone. e.g. the diagram could be $5\longrightarrow j_1\longrightarrow j_2\longrightarrow\cdots\longrightarrow j_m\longrightarrow k$ if the first person in the line (lost his ticket) seats at seat #5. right? – athos Oct 1 '13 at 1:18
• 1. $\prod_{i\in I}(1+x_i)=\sum_{J\subseteq I}\prod_{j\in J}x_j$ – user940 Oct 1 '13 at 12:13
• 2. No, any bumping can be traced back to passenger 1. – user940 Oct 1 '13 at 12:14
• thank you for your explanation. for point 1, after drawing it out i finally understand it. but for point 2, could you please elaborate a bit more? scenario A: the first person in the line bumped into seat #1, customer #1 then bumped into seat #5, this is $1\longrightarrow j_1=5\longrightarrow j_2\longrightarrow\cdots\longrightarrow j_m\longrightarrow k$; Scenario B: the first person in the line bumped into seat #5, customer #5 then bumped on, this is $j_1=5\longrightarrow j_2\longrightarrow\cdots\longrightarrow j_m\longrightarrow k$ -- these are 2 different scenarios right? – athos Oct 1 '13 at 15:05
• +1 for the reference! here's a link to it – Matt Aug 19 '14 at 2:09

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.

• Your answer is correct. I just would like to add that people can still be in the wrong seats. However, all unoccupied seats will have their people from that point on. – user4951 Feb 26 '18 at 7:18
• For example, 1 can seat in 2. 2 can seat in 3. And 3 can sit in 1. So all 3 are in the wrong seats. But seat 4-100 will all be unoccupied – user4951 Feb 26 '18 at 7:18
• -1. "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." That is just plain wrong. It is not $1/2$ at every stage except the last. – Hans Jun 10 at 6:43

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.

I tried to synthesize the proof for myself from stuff I've read to get rid of all calculations (somehow I found the argument that "each person's choice is 50-50 between good and bad once we throw away the irrelevant stuff" convincing but hard to formalize).

Claim 1: when the last passenger boards, the remaining empty seat will either be his own or the first passenger's.

Proof: If the remaining empty seat belongs to passenger $n \neq 1, 100$, then passenger $n$ should have sat there.

Claim 2: if at any time a passenger other than the final passenger finds her seat occupied, then both the seat assigned to the first and to the final passenger will be free.

Proof: If not, then there is a nonzero probability that after this passenger makes a decision, both the first and last seats will be occupied. This contradicts Claim 1.

Claim 3: There is a bijection between the set of admissible seatings in which the final passenger gets his seat and the set where he doesn't.

Proof: Suppose for an admissible seating $S$ that passenger $n$ is the first to choose one of {first passenger's seat, last passenger's seat}. By claim $2$, there is a unique admissible seating $T$ which agrees with $S$ except that passenger $n$ and the final passenger make the opposite decision ($T$ matches $S$ until passenger $n$ sits, then by Claim 2, $T$ must continue to match $S$ until the final passenger).

• This is the best proof so far! – tuko Oct 31 '16 at 13:06

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$$.

There are many ways to come up with this answer, but here’s one that makes sense to me. For ease of explanation we’ll say that I’m the first person to sit down and you’re the last. Also if you sit in your own seat then you “win”, otherwise you “lose”.

Let’s say that there are only two seats, yours and mine. If I sit in my own seat, you win. If I sit in your seat, you lose. So you have a $$50\%$$ chance of winning.

Now let’s go back to $$100$$ seats. The previous paragraph still holds true: you have a $$50\%$$ chance of winning if we only consider your seat and mine. Now if I sit anywhere else, I’m just postponing the decision. Let’s say I sit in the seat of the person who’s 13th in line. Persons $$2$$ through $$12$$ will sit in their own seats, then when person $$13$$ comes in he can either sit in my original seat (and you win) or yours (and you lose). Or of course he could sit anywhere else and postpone the decision again.

If this keeps going, then eventually there are only two seats left and person $$99$$ is forced to choose either your seat or mine, again with 50% chance. There are only two seats that matter throughout the game: yours and mine. Any sitting in other seats is just postponing the decision of which of the two interesting seats gets sat in first. Note also that you’ll only ever end up in your seat or mine, no one else’s.

It’s a bit like flipping a coin, except that you can postpone flipping, but not indefinitely. What’s the chance of coming out heads? Well $$50\%$$, the postponement doesn’t change that.

Here’s a mathematical way to see it. Define $$f(n)$$ to be the chance that the last person in an airplane of n seats will get his own seat. It can be defined recursively like this: $$f(n)=\frac1n\cdot1+\frac{n−2}n\cdot f(n−1) + \frac1n\cdot 0$$

The first term is the chance that the first person will sit in his own seat $$\frac1n$$ multiplied by the chance, then, that the last person will sit in his own $$1$$. The last term is the chance that the first person will sit in the last person’s seat $$\frac1n$$ multiplied by the chance, then, that the last person will get his own seat $$0$$. The middle term counts every other seat. There are $$n−2$$ other seats, and there’s a $$\frac1n$$ chance of each, and they all simplify to the $$f(n−1)$$ case. Also $$f(2)=0.5$$.

If you plug in $$0.5$$ for the $$f(n−1)$$ term, you find that $$f(n)=0.5$$, so it’s true for any $$n>1$$.

I thought I'd add another solution that uses recursion. Let $$p_n$$ be the probability that the n-th person gets the n-th seat (his own seat) and $$q_n=1-p_n$$ the probability that he does not. Then,

$$p_n=\underbrace{1/n}_{\text{1-st person sits in 1-st seat}}+\underbrace{(n-2)/n}_{\text{1-st person does not sit in the 1-st or n-th seat}} \times p_{n-1}$$ $$q_n=\underbrace{1/n}_{\text{1-st person sits in n-th seat}}+\underbrace{(n-2)/n}_{\text{1-st person does not sit in the 1-st or n-th seat}} \times q_{n-1}$$ Now substitute in $$q_n=1-p_n$$ to get $$p_n=q_n=1/2$$.

Edit: I should add that initially I just thought it was as simple as plugging one equation into the other but indeed an inductive argument is needed like @ely's answer.

Edit: my answer assumes that $$p_i=p_j$$ - basically I haven't taken into account that probabilities might be different depending on which seat the 1-st person sits in (as stated by @hans)... The answer might be salvageable if one instead defines $$p_n$$ as the probability that everyone on a plane with $$n$$-seats all sit in their own seat but not sure as this might make some other implicit assumption.

• @Hans Could you provide a bit of extra explanation as I don't understand where I (and some of the other answers) make this assumption? – user103828 Jun 9 at 11:10
• The term in the first equation comes from assuming $\underbrace{\frac{n-2}{n}}_{\text{1-st person does not sit at the 1-st or n-th seat}} \times p_{n-1}=\sum_{i=2}^{n-1}\underbrace{\frac1n}_\text{1-st person sits at the i-th seat} p_i$ where $p_i$'s are all the same $\forall 2\le i\le n-1$. – Hans Jun 9 at 18:12
• Do you agree with my comment regarding the flaw of you solution above? Why did you or someone else delete my first comment? – Hans Jun 10 at 17:18
• ok, I agree (and added an edit to this effect). I don't have permission to delete your comments – user103828 Jun 10 at 20:02
• @Shashank has already derived long before the constancy $\frac12$ of $p_n$ for all $n$. – Hans Jun 11 at 0:46

It is possible to count the different configurations of interest to calculate the probability directly, by formalizing some of the ideas already presented.

In an allowed configuration, denote a displacement of one or more passengers with the diagram $i\rightarrow j$ whenever passenger $i$ displaces passenger $j$ from their assigned seat ($i < j$).

Suppose C is an allowed configuration with a displacement D of passengers, say, $...i\rightarrow j...$ Clearly i has a predecessor (which can be added to the diagram) or i is passenger 1, since the problem states that only passenger 1 is free to displace passengers without being displaced themselves. Since each predecessor must represent a passenger who boarded earlier, of which there are a finite number, using this argument at most i times, shows that D must begin with passenger 1. By a similar argument, D must have a last passenger which chooses passenger 1’s seat to end the displacement.

If E is a displacement in C, by the same argument it must start with passenger 1, followed by the choices already indicated in D, so that E is the same as D. Clearly, two allowed configurations are the same if and only if their displacements are the same. Additionally, note that a displacement of the form, $\textstyle\ 1\rightarrow i \rightarrow … \rightarrow j$ where {i,…,j} is a subset of {2,…,100} in increasing order, always specifies a valid configuration. Hence,

There is a bijection between the set of allowable configurations and diagrams of the form $1\rightarrow i \rightarrow … \rightarrow j$ where {i,…,j} is a subset of {2,…,100} in increasing order.

Now count configurations by counting the diagrams. Write 1 as the diagram for the null displacement in the configuration where all passengers sit in their assigned seats. Note that this is same as counting all subsets of a two particular sets, so the probability that the final passenger is sitting in their assigned seat is:

$\textstyle \frac{\textrm{Number of all diagrams of the form } 1\rightarrow i \rightarrow … \rightarrow j\textrm{ where {i,…,j} is a subset of {2,…,99} in increasing order}}{\textrm{Number of all diagrams of the form } 1\rightarrow k \rightarrow … \rightarrow l\textrm{ where {k,…,l} is a subset of {2,…,100} in increasing order}} = \frac{2^{98}}{2^{99}} = \frac{1}{2}\\$

Call the passengers $P_1,\dots,P_n$ in the order in which they board, and let $S_i$ be the seat assigned to $P_i$.

Consider the first moment at which a passenger $P_i$ sits in either $S_1$ or $S_n$. The other one of those seats is empty, so the passengers haven't all boarded yet, so $i\ne n$.

If $i=1$, $P_i$ takes a random seat as per the OP.

Otherwise, $i\ne 1$ and $i\ne n$, so the reason why $P_i$ picked $S_1$ or $S_n$ is that $S_i$ was already occupied. So in this case, $P_i$ takes a random seat as per the OP.

Thus in both the above cases, this moment is when a passenger takes a random seat. They are equally likely to pick $S_1$ as $S_n$. Thus each of the two cases below occurs with probability $1/2$.

If $P_i$ picked $S_n$, then $P_n$ will not get their assigned seat $S_n$.

If $P_i$ picked $S_1$, then the cycle of displacement of Bruce's proof ends, and everyone who has not yet boarded gets their assigned seat, including $P_n$.

Thus the answer is $1/2$.

• Although several answers have been posted, I felt that those that were not over-complicated were unsatisfactory for one reason or another: Aryabhata's was too unclear; Matt posed a different problem and its solution, without proving that the OP had the same answer; David Lewis's is wrong (as J Chang pointed out); the "proofs" in hunter's are just further claims which lack proof; Bruce's fails to prove that the two possibilities are equally probable (on which point I agree with Michael Albanese). – Rosie F Mar 24 '18 at 20:52

The other answer that uses recursion to define $p_{n}$ and $q_{n}$ is very light on details and makes it sound as if you can directly solve of $p_{n} = q_{n}$ from the two equations.

Note that the two equations

$$p_{n} = \frac{1}{n} + \frac{n - 2}{n}p_{n-1}$$ $$q_{n} = \frac{1}{n} + \frac{n - 2}{n}q_{n-1}$$

don't offer independent constraints on the variables since $p_{n} = 1 - q_{n}$. So subtract the equations $p_{n} - q_{n}$:

$$p_{n} - q_{n} = \frac{1}{n} + \frac{n - 2}{n}p_{n-1} - \frac{1}{n} - \frac{n - 2}{n}q_{n-1}$$ $$p_{n} - q_{n} = \frac{n - 2}{n}(p_{n-1} - q_{n-1})$$

At this point we can state for the base case, $n=2$, we know $p_{2} = q_{2} = \frac{1}{2}$. Now if we assume $q_{n-1} = p_{n-1}$, clearly the right-hand side of our last equation becomes zero, and $q_{n} = p_{n}$.

Since $q_{n} + p_{n} = 1$, then $\boxed{p_{n} = q_{n} = \frac{1}{2}}$.

It's just important to note that after setting up the problem recursively, you still need to appeal to induction to derive the solution. It's not as simple as algebraic manipulation of the definition of $p_{n}$ or $q_{n}$ even though this is how the other solution makes it sound.

• your last recursion involving q_n-p_n follows directly from "the two equations" by subtraction. – PatrickT Mar 5 '18 at 15:12
• @PatrickT Thanks for mentioning that. I simplified the algebra by re-writing it with this subtraction as you pointed out. – ely Apr 17 '18 at 21:06
• -1. This derivation presumes $p_i=p_j,\forall\, 2\le i<j\le n-1$. This is not right. – Hans Jun 8 at 2:56
• @Hans you are mistaken. Can you state where you think an assumption enters the solution and we can help to resolve your confusion about it? – ely Jun 10 at 12:50
• In the equation $p_{n} = \frac{1}{n} + \frac{n - 2}{n}p_{n-1}$, how do you get the second term which should originate from $\sum_{i=2}^{n-1}\frac1n p_i$? How do you simplify the summation if not presuming the equality of all the probabilities $p_i$'s of the $i$'th passenger sitting in the $i$'th seat in a $i$-seat plane? The presumption is without proof. That is why the derivation is flawed. – Hans Jun 10 at 17:17

My answer owes much to what went before , but it works for me. The first person in the queue ( assume he does not sit in his own seat by random chance) displaces one person still in the queue by sitting in their seat . Passengers continue to board in their own seats until the displaced person comes to sit down. His own seat is taken so he in turn displaces someone else who is in the queue. There is always one displaced person in the queue as this cycle continues From here there are only 2 possible outcomes, a) a displaced person randomly choses the first mans seat at which point the cycle of displacement ends and the boarding can then continue to the end person with everyone else including the last man getting their own seat or b) The last mans seat is selected by a displaced person then there is no more displacement until the last man tries to sit down and will find his seat full

Whichever of a ) or b ) happens first will determine whether the last mans seat is available when he comes to board. a) or b) are 2 events determined by random chance therefore each has 50% chance of happening Hence answer = 1/2 or 50%

• It's not clear to me that $(a)$ and $(b)$ are equally likely, but it seems like a good heuristic. – Michael Albanese Jan 27 '16 at 13:51
• this is correct. It's like Matt's answer – user4951 Feb 26 '18 at 7:22
• -1. Wrong derivation. "a) or b) are 2 events determined by random chance therefore each has 50% chance of happening Hence answer = 1/2." Having two random possibilities does not mean at all that each probability is $1/2$. – Hans Jun 10 at 5:44

## protected by Zev ChonolesMay 27 '16 at 2:46

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).