The Airplane Problem

2 minute read

Here’s a neat little problem I came across when solving some probability puzzles. It took me a couple of hours to realize the solution, and it took my younger brother around 30 minutes for a much more elegant solution. Both are detailed below.

Problem StatementPermalink

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. What is the probability that the last person that boards will end up in his/her proper seat.

SolutionPermalink

The answer can be arrived at by working backwards.

Refer to the nth person by Pn. Let pn denote the probability that P100 gets their proper seat assuming P1 occupies Pn’s seat. Now, consider the case where P1 occupies Pn1’s seat. Then there are two possibilites:

  • Pn1 occupies P1’s seat
  • Pn1 occupies Pk’s seat, k[n,100)

In the first case, PnP100 will all occupy their corresponding “proper” seats. Further note that the second case is the same as if P1 had occupied Pk’s seat, for which the probability that P100 gets their seat is pk. In both situations, the chances of Pn1 picking any seat are 1100(n1)+1. Therefore,

pn1=(1102n+100k=n1102npk)=1102n(1+100k=npk)

Clearly, pn|n=100=0. Using the relation derived above, we can calculate p99 as p99=12(1+0)=12. Similarly, p98=13(1+12+0)=12. In fact, pk=12 for all k such that 1k<100. Lastly, note that each of these cases can occur with a probability of 1100, since P1 can choose Pk’s seat randomly with a probability 1100. Therefore, the probability of P100 getting their proper seat is

p=1100100k=1pk=11001002=12

Elegant SolutionPermalink

The following solution might possibly blow your mind, and it is fitting that my brother came up with it. Let us say P1 takes Pk’s place for some k[1,100). Then P2Pk1 will take their proper seats. Further, a closed “chain” of seat occupancy, where Pk can occupy someone else’s seat, who further can occupy a third’s seat. This closed “chain” will always end with someone occupying P1’s seat.

For example, for some n(k,100), Pk can occupy Pn’s seat, and Pn can occupy P1’s seat to form the chain, P1PkPnP1. For P100 to get their “proper” seat, they should be absent from this chain. Therefore,

p=No. of chains where P100 is absentTotal no. of chains=2992100=12

Note that the no. of possible such “chains” given N people is 2N since each person can either be present or not be present in the chain.

Leave a comment