The lost boarding pass and the seven dwarfs

Imagine a group of 100 Icelanders boarding a plane from Reykjavík to Tenerife. They board one at a time. The first person who ascends the stairs to the plane lets his boarding pass fall from his hands and sees it twirling down through the stairs and under the plane. He decides not to go down and to pick up his boarding pass in order to see what his seat number is. He enters the plane and chooses at random a seat.

Icelanders are relaxed people. Therefore every next person who finds his assigned seat occupied does not worry about it and chooses at random another free seat. What are the chances that the last passenger entering the plane finds his “own” seat free? This is the famous lost boarding pass puzzle proposed by Peter Winkler.

The surprising answer to the posed question is that the probability of the last passenger finding his own seat free is 50%. How do we get this answer? We provide two solution approaches. A useful problem-solving strategy in mathematics is to consider first a reduced version of the problem that is easier to solve. Taking this problem-solving strategy, let us first consider the trivial case of two passengers boarding a two-passenger plane. The last passenger gets his own seat only if the first passenger happens to choose his own seat. Therefore the probability of the last passenger finding his seat free is 50%. Thus, for , we have , where , where is defined as the probability that the last passenger finds his seat free when there are passenger boarding on an -passenger plane. Next consider the case that three passengers are boarding a three-passenger plane. Then, by conditioning on the choice of the first passenger, we have

The argument is simple. If the first passenger takes his own seat, the second passenger can take his assigned seat and then the last passenger will find his own seat free. However, if the first passenger chooses the seat of the second passenger, then we can reduce the problem to the previous case of two passengers for a two-passenger plane by imagining that the seat of the first passenger becomes the seat of the second passenger, with the second passenger playing the role of the first passenger. The equation for gives Similarly, in the case of four passengers boarding on a four-passenger plane, we find that the problem reduces to the problem if the first passenger chooses the seat of the second passenger; it reduces to the problem if the first passenger chooses the seat of the
third passenger. Thus

 Continuing in this way, we find by induction that

  for any 

This is a remarkable result, which cries for an intuitive explanation without mathematical formulas. Such an explanation is as follows. The key observation is that the last free seat is either the seat of the first passenger or the seat of the last passenger. This is an immediate consequence of the fact that any of the other passengers always chooses his own seat when it is free. Each time a passenger finds his seat occupied, the passenger chooses at random a free seat; at that point, probability of the first passenger’s seat being chosen is equal to the probability of the last passenger’s seat being chosen. The scenario that the probability of the first passenger’s seat being chosen is equal to the probability of the last passenger’s seat being chosen also applies to the first passenger. Thus, the last free seat is equally likely to be either the seat of the first passenger or the seat of the last passenger.

An amusing variant of the problem is the bed problem of the seven dwarfs. Each of the seven dwarfs has his own bed in a common dormitory. Every night, they retire to bed one at a time, always in the same sequential order with the youngest retiring as first and the oldest retiring as last. On a particular evening, the youngest dwarf has had too much to drink. Randomly selecting one of the seven beds, he casts himself upon it and promptly falls asleep. As each of the other dwarfs retires, he chooses his own bed if it is not occupied, and otherwise randomly chooses another unoccupied bed. What is the probability that the oldest dwarf can sleep in his own bed?

To conclude this column, let us consider the following variant of the problem with the seven dwarfs. The jolly youngest dwarf intentionally decides not to choose his own bed but rather to choose at random one of the other six beds. Then, the probability that the oldest dwarf can sleep in his own bed is , as can be seen by using the intuitive reasoning above.

Henk Tijms is Honorary Fellow of the Tinbergen Institute. He has written many papers on applied probability and stochastic optimization. Also, he is the author of several textbooks. His latest book is Probability: A Lively Introduction, Cambridge University Press, 2017.