Following are a couple of related puzzles, motivated by this holiday season:
1. You are standing at the very end of a line of 100 holiday travelers (you and 99 others) waiting to board an airplane. Each passenger in line has a boarding pass assigning him or her to one of the 100 seats on the airplane. However, the first person in line is rather confused, and so instead of sitting in her assigned seat, she boards the airplane and simply selects a seat at random (possibly her own). As each subsequent passenger boards the airplane, he sits in his assigned seat if it is empty, or selects an empty seat at random if it is not. What is the probability you, the last person to board, will be able to sit in your assigned seat?
2. Preparing to return home after the holiday, you find yourself once again last in a line of 100 travelers waiting to board an airplane. This time, it is not just the first person in line who is confused; after a stressful holiday with their families, now every person in line is not just confused but deranged. That is, each passenger in turn boards the airplane and selects a seat at random from all currently empty seats, excluding their own. What is the probability that you, the last person to board, will be forced to sit in your assigned seat?
The first problem is an oldie but a goodie. I like it because it can be approached in several different ways. It is easy to simulate using a computer, which quickly leads to conjecture at the solution. Given the conjecture, the proof is a nice application of mathematical induction. But there are also nice symmetry arguments via which the problem may be solved more directly.
The second problem is more difficult, and is the real motivation for this post. Solutions to both are welcome in the comments– until then, consider in what other way(s) this second problem might arise in relation to the holidays?