The puzzle: One hundred people line up to board a plane with 100 seats. The first person in line is has lost his boarding pass, so he randomly chooses a seat. After that, each person entering the plane either sits in their assigned seat, if it is available, or, if not, chooses an unoccupied seat randomly.
When the 100th passenger finally enters the plane, what is the probability that she finds her assigned seat unoccupied?
A solution: The probability, somewhat surprisingly, is 1/2! There are long ways to see this, and short ways ... let me describe what I think is the shortest solution that is still fairly complete.
The key observation is this: when the last person boards, the only possibilities for empty seats are the correct seat, or the seat assigned to the first person. Why? well, if the seat assigned to the 16th person to board is free when the last person boards, then it was also free when the 16th person boarded, so she would have taken it then, a contradiction; and the same contradiction works for everyone else after the first person to board.
A corollary of this observation is that whenever a passenger makes a random choice, both the first person's and last person's seat must be available. For if, after one of these seats is taken, a passenger comes on and finds that she has to make a random selection between many seats, there is a non-zero probability that she takes the other of these two special seats, contradicting the key observation (since it forces the last passenger to sit somewhere other than her own seat or the first person's seat, a situation we now know to be untenable).
Armed with the key observation, we see that the event that the last person's correct seat is free, is exactly the same as the event that the first person's seat was taken before the last person's seat. What could be the probability of that? Well, each person who came on the plane and had to make a random choice, was equally likely to choose the first person's seat or the last person's seat - the random chooser exhibits absolutely no preference towards a particular seat. This means that the probability that one seat is taken before the other must be 1/2.
Another way to think of this last part: if you tried to write down two exact expressions, one (A) for the probability that the first person's seat is taken before the last person's seat, and one (B) for the probability that the last person's seat is taken before the first person's seat, these two expressions would have to be identical, since every time a random choice is made, the probability of the first person's seat being chosen is equal to the probability of the last person's seat being chosen. Since A=B, and this covers all possibilities (by the key observation), they must both be equal to 1/2.
I learned this puzzle from Peter Winkler's book ``Mathematical Puzzles (A Connoisseur's Collection)'' (where he gives the solution described above). It also appears in Bela Bollobas' ``The Art of Mathematics (Coffee Time in Memphis)'', where a different solution is given. A few years ago, it made it to the NPR radio program ``Car Talk'' (see here for a transcript of hosts Tom and Ray telling the problem, and here for their discussion of the solution). Google ``The Lost Boarding Pass puzzle'' for lots of webpages discussing it.