Airplane puzzle: Slick solution?

N (> 1) passengers are about to board, one at a time, an airplane with N seats. Each passenger has an assigned seat. On the way to his seat, the first passenger to board loses his boarding pass, so he selects a seat at random Each subsequent passenger sits in his/her assigned seat if it is not already taken; otherwise, s/he selects at random an empty seat. What is the probability that the last passenger to board (i.e., the Nth passenger) sits in her assigned seat?

Below, I give a solution to this problem. However, this problem appeared in a popular, non-mathematical forum, and my solution strikes me as a bit too mathematically/probabilistically sophisticated for the (wo)man on the street. Does anyone have an explanation that is less sophisticated?

[spoiler space follows] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Answer: 1/2.

[more spoiler space before justification] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Justification: Let p_i be the desired probability when N = i. We show by induction that p_i = 1/2. It is clear that p_2 = 1/2.

Let N = n, and assume p_i = 1/2 for i < n. Condition on the seat the first passenger takes. The probability he takes any particular seat is 1/n. If he takes his assigned seat, the last passenger gets her assigned seat with conditional probability 1. If the first passenger takes the last passenger's seat, the latter gets her seat with conditional probability 0. Otherwise, the first passenger takes the seat of the Mth passenger to board (1 < M < n); in this case, the problem reduces the case that N = n - M + 1, since the Mth passenger may take either the first passenger's seat or some other seat. Thus, p_n = 1/n + (1/n) sum(i = 2..n-1, p_i) = 1/2 by induction. q.e.d.

: the first passenger to board loses his boarding pass, so he selects a : seat at random Each subsequent passenger sits in his/her assigned seat : if it is not already taken; otherwise, s/he selects at random an empty : seat. What is the probability that the last passenger to board (i.e., : the Nth passenger) sits in her assigned seat?

: Below, I give a solution to this problem. However, this problem : appeared in a popular, non-mathematical forum, and my solution strikes : me as a bit too mathematically/probabilistically sophisticated for the : (wo)man on the street. Does anyone have an explanation that is less : sophisticated?

The last passenger sits in his assigned seat if and only if the first passenger's seat is taken before the last passenger's seat.

As long as both of these seats are empty, they are either both available (with equal probability), or both not available, to any particular passenger. (Note that this includes the first passenger, who sits in a random seat.) Therefore, both seats have the same probability of being taken first

See also http://www.cartalk.com/content/puzzler/transcripts/ 200440/answer.html , which gives the same argument. I didn't know the source of this puzzle until after I posted.

Ahhhh ... verrrrrrrry slick!

This puzzle, under the name 'The Lost Boarding Pass,' appears on page 35 of Peter Winkler's book, Mathematical Puzzles. Winkler writes that he heard it at Gathering for Gardner V (the 5th in a series of meetings for Martin Gardner), and that Ander Holroyd supplied the version Winkler published.

The sequence is as likely to finish with seat i_j chosen as with seat N chosen; in the first case, person N gets the correct seat, in the second case person N doesn't. Hence the two events each have probability 1/2.

Another approach is to change the rules slightly.

The passing on of the responsibility to find random seats confuses the matter slightly.

When the first person sits in a wrong seat that's not yours, instead of bumping the other person he apologises, lets the other person have his rightful seat, and continues chosing randomly.

It's the same situation as before, there's still precisely one person who will be randomly selecting a seat. It just so happens it's now always passenger #1. So the only question remains - does #1 sit in his own seat or your seat first? If the former, you get your seat, if the latter, you don't.

Kudos where kudos due: The Winkler book was published in 2003, and the Gardner meeting was held the year before. The first instance of equivalently worded puzzle that I could find was in fact by Gerry Quinn on Apr-30th-1997 in the article: