The Lost Boarding Pass

On a sold out flight, 100 people line up to board the plane. The first passenger in the line has lost his boarding pass, but was allowed in, regardless. He takes a random seat. Each subsequent passenger takes his or her assigned seat if available, or a random unoccupied seat, otherwise. What is the probability that the last passenger to board the plane finds his seat unoccupied?

Solution

Copyright © 1996-2010 Alexander Bogomolny

When the last passenger boards the plane, there are just two possibilities: the one remaining seat may be his or that of the first passenger. Under the assumption that no preference has been exhibited by the boarding passengers towards either of the two seats, they both have the same probability to become the last unoccupied seat: 50%.

Suppose there are n ≥ 2 passengers and n seats.If, for any k < n, the first k passengers occupy assigned to them (as a group, not individually) then from then on everybody, including the last passenger, sits on his own seat. Also, if one of the first k < n passengers occupies the seat of the last passenger then the last passenger will not sit in his own seat. Now, if, for k - 1, neither of these events holds then the k^th passenger's choice has exactly as much chance of leading to the first event as to the second: if his own seat is unoccupied, neither of the events will happen, and if his own seat seat is occupied then there is exactly one (unoccupied) seat, the first, that leads to the first event and exactly one (unoccupied) seat, the last, that leads to the second.

B. Bollobás notes that this question was on Car Talk, the popular NPR program airing on Saturdays, and was brought to his attention by Oliver Riordan, who also gave the proof above. Also, note that the full plane is important. If there are more seats than the passengers then it is more likely that the last passenger sits in his own seat.

References

1. B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006, p. 176.
2. P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004, pp. 35-37

Copyright © 1996-2010 Alexander Bogomolny