One seat left. Is it yours?
Car Talk, National Public Radio, 4 October 2004

The puzzle for this week's Car Talk was:

One hundred people line up to board an airplane, but the first has lost his boarding pass and takes a random seat instead. Each subsequent passenger takes his or her assigned seat if available, otherwise a random unoccupied seat. You are the last passenger. What is the probability that you get your own seat?

You and your students would enjoy this puzzle if you have not seen it before. It has not made Marilyn vos Savant's column yet but it is in Peter Winkler's nice book: Mathematical Puzzles: A Connoisseur's Collection where it is called "The lost boarding pass puzzle."

This puzzle also appeared in the March/April 2003 issue of the Journal Contingencies. This journal is published quarterly by the American Academy of Actuaries and includes a puzzle column edited by Noam Segal. Not surprisingly, these puzzles often involve probability or statistical concepts.You can see the current puzzle and the answer to the previous puzzle at the Contingencies website. Earlier puzzles are archived at the Nebraska Actuaries Club website. You will find other questions relating to the lost boarding pass puzzle in the May/June 2003 issue and the solutions to these and the original puzzle in the July/August, 2003 issue.

After we discussed this problem in Chance News 13.05 , reader Jerry Grossman wrote us:

There is a much richer history to the boarding pass problem than you suggest in Chance News 13.05. Please see The College Math Journal, vol. 34, no 4, Sept 2003, pages 332-333.

Here we find that the" Lost boarding pass problem" is problem number 735 in the September 2003 College Math Journal. The problem described here is the same as the Car Talk problem except that it occurs on a tour bus with n seats. A number of people provided solutions and the Problem Editor describes two of the solutions. The editor also reported that The Con Amore Problem Group pointed out that this problem, with a different setting, appeared in the December 2001, (vol. 15, no 2, p4) issue of the journal FAMØS published by the University of Copenhagen. FAMØS is in Danish but Lise Richardson (the Danish member of our Bach Study Group), Peter Doyle and Taus Brock-Nannestad helped us with the translation of this and later articles). Here is how the problem is posed in FAMØS:

The mermaid lounge

There are n nissers (A nisser is type of gnome or elf associated with Danish Christmas) who have their beds in a big common dormitory. Nissers are normally very disciplined, so they go to bed one by one. Last year's Christmas party caused the first nisser to have too much to drink, and as he was going to bed (as the first one) he chose a random bed instead of his own. The rest of the nissers took their own beds, but if the bed had already been taken, they took a random one. What is the probability that the nth nisser gets his own bed?

This problem was solved by Henning Makholm in the March 2002 (vol. 15, no 3, p17) issue of FAMØS. Makholm also proposed a bonus problem: find the probability that the kth nisser gets his own bed. In the May 2002(vol. 15, no4, p8) FAMØS this bonus problem was solved by Rolf Dyre Svvegstrup who showed that the probability that the kth nisser gets his own bed is (n-k+1)/(n-k+2).This also solves the lost boarding passenger problem which is the case k = n. Note that the answer is 1/2 for this case. His proof is:

When the k'th gnome goes to bed, the beds numbered 2 to k-1 are guaranteed to be taken. None of the first k gnomes have distinguished between the remaining n-(k-1) beds, and the probability that the k'th bed is taken is thus 1/(n-(k-2)). The probability that the k'th gnome gets his own bed is thus 1-1/(n-(k-2)). In the case of k = n this is exactly 1/2 as Henning demonstrated in the last issue.

This is similar to Peter Winkler's solution to the original problem with k = n:

We merely need to observe that when the 100th passenger finally boards, the seat remaining will be either the one assigned to him (or her) or the one assigned to the first passenger. Every other seat has been taken either by its rightful owner or by someone else who got there first.

Since there has been no preference exhibited at any stage toward one of the other of those two seats, the probability that the 100th passenger gets his own seat is 50%.

We found that, to understand these proofs, it helps to describe why they are correct in terms of an example.

Consider the special case n = 10 and k = 6. We assume that the beds are numbered from 1 to 10 and the nissers are numbered according to their bed number.

We shall show that one of the first 5 nissers must choose one of the beds 1,6,7,8,9,10 at a time when when all these beds are available and, when this happens, the probability that nisser 6 gets his own bed is 5/6. This agrees with Rolf's result since (10-6+1)/(10-6+2) = 5/6.

We claim that one of first 5 nissers will choose one of the beds 1,6,7,8,9, or 10. If not, the first 4 nissers would have to choose bed 5 or else 4 nissers would have to occupy beds 2,3,4. Then nisser 5 would have to choose from beds 1,6,7,8,9 or 10. Now, assume that nisser m<6 is the one who chose bed 1,6,7,8,9, or 10. Then nissers m+1 to 6 will all get their own beds. So, given that m chooses 1,7,8,9, or 10 the probability that nisser 6 gets his own bed is 5/6.

In the general case with n beds, to find the probability that the kth nisser gets his own bed we use the same argument with bed 6 replace by bed k and beds 1,6,7,8,9, or 10 replaced by beds 1,k,k+1,k+2...n. Then the probability that nisser k gets his own bed is (n-k+1)/(n-k +2).

DISCUSSION QUESTIONS:

(1) What is the expected number of nissers who get their own seats?

(2) What is the probability the kth nisser gets his own seat fro k > 2 if the first two nissers are drunk?