The Airplane Problem
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 Pn−1’s seat. Then there are two possibilites:
- Pn−1 occupies P1’s seat
- Pn−1 occupies Pk’s seat, ∀k∈[n,100)
In the first case, Pn→P100 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 Pn−1 picking any seat are 1100−(n−1)+1. Therefore,
pn−1=(1102−n+100∑k=n1102−npk)=⋅1102−n(1+100∑k=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 1≤k<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=1100100∑k=1pk=1100⋅1002=12Elegant 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 P2→Pk−1 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, P1→Pk→Pn→P1. 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=12Note 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