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

This week's Car Talk puzzle asked:

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's column yet but it is in Peter Winkler's very nice new book: Mathematical Puzzles: A Connoisseur's Collection where it is called "The lost boarding pass puzzle." You can find the solution to this puzzle at the end of this Chance News.

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. We include two of these in our discussion questions.

DISCUSSION QUESTIONS:

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

(2) Under the same conditions as the original problem what is the probability the last person gets his/her own seat if the first two people lose their boarding passes?

Answer to the "lost boarding pass" puzzle.

First we consider a smaller example:

Passenger 1 has lost his boarding pass and so randomly chooses a seat. He chooses seat 7 which was assigned to passenger 4. Then passengers 2 and 3 sit in their assigned seats (3,8) and passenger 4 finds his seat taken so randomly chooses a seat from the seats that are free which are the seat of passenger 1 (6) and the assigned seats for passengers behind him in the line (10, 4, 9, 2, 5 1). He chose seat 9 which was assigned to passenger 7. Thus passengers 5 and 6 get their assigned seats (10,4) and 7 must choose a seat randomly from passenger 1's seat (6) and seats assigned to those after him (2,5,1). Passenger 7 chooses seat 1 which was assigned to passenger 10. Now passengers 8 and 9 will get thier assigned seats (9,2) and passenger 10 will have to take passenger 1 seat (6) and everyone has a seat. Had 7 chosen passenger 1's seat then passenger 10 would have his assigned seat. Since passenger 7's choice was a random choice, given that he chose either the seat assigned to the first or last passenger the probability that he chose the seat assigned to passenger 1 is 1/2, so this is the probability that the last passenger gets his assigned seat.

As the above example shows, when the first passenger chooses a random seat, either he chooses the seat assigned to him or the last passenger or he sets in motion a sequence of passengers who find their seats occupied and have to make random choices among the seats available. This sequence continues until a passenger's random choice is either the seat assigned to the first or the last passenger. This must happen before the next-to -last passenger boards since if it does not happen until then, then he would have three seats to choose from: his seat, that of the first passenger, and the last passenger's seat. But that is impossible since he and the last passanger are the only passengers without seats.

Thus one and only one random choice will result in choosing either the first or last passangers seat. Given that this happens there is an equal chance that it is the first or the last person's seat. Thus the probability that the last person gets the seat assigned to him/her is 1/2.

In Chance News 13.05 we discussed the "Lost boarding pass" problem that appeared on the the Oct. 4 Car Talk program. Jerry Grossman wrote us about the history of this problem:

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.

The"Lost boarding pass problem" is number 735 in the College Math Journal and was proposed by two readers one of whom was Jerry.

The problem described here is the same as the car talk problem discussed in Chance News 13.05 except that it occurs on a tour bus with n > 1 seats. A large number of people provided solutions and the Problem Editor describes two of the solutions.

The editor remarks that The Con Amore Problem Group pointed out that this problem, with a different setting, appeared in the December 2001, (vol 15, no2) issue of the journal FAMØS published by the University of Copenhagen. Solutions and a generalization appeared in the March and May, 2002 issues of FAMØS. These issues are available in pdf format on the FAMØS website. They are in Danish but Peter Doyle and Lise Richardson (our Danish member of our Bach Study Group) provided us with a translation of the articles. Here is the version of the problem provided in FAMØS and appropriate for the Holiday period when this Chance News was written:

The mermaid lounge

There are n nisses (a type of gnome or elf associated with Danish Christmas) who have their beds in a big common dormitory. Nisses are normally very disciplined, so they go to bed one by one. Last year's Christmas party caused nisse # l 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 nisses took their own beds, but if the bed had already been taken, they took a random one. What is the probability that nisse # n gets his own bed?

The problem was solved by Henning Makholm in the March 2002 issue of FAMØS who also proposed as a bonus problem to find the probability that the kth nisse gets his own bed. This problem was solved by Rolf Dyre Svvegstrup who showed that the answer is:

Note that when k = n, the answer is 1/2 in agreement with the original problem. Rolf's proof is very short and as usual we had trouble being convinced without working an example. So here is our example which we convinces us, but is probably more complicated than what Rolf had in mind.

We assume that the nisses beds are number according to the order that they come in. Assume that there are 7 nisses and we want to find the probability that the 5th nisse gets his own bed. The first nisse chooses randomly from all the 7 beds. If he chooses bed 1,5,6, or 7, nisse 5's fate is settled and he gets his own bed with probability 3/4. If not he chooses from 2,3,4. Suppose he chooses bed 3. Then the 3rd nisse must make a random choice from 1,5,6,7 or 4. Again if he chooses from 1,5,6,7, nisse 5's fate is settled and he gets his own bed with probability 3/4. His only other choice is 4, but if he chooses this, nesse 4 has no choice but to choose from 1,5,6,7 and again nesse 5 will get his own bed probability 3/4.