PUZZLE #6: LOST BOARDING PASS (SOLUTION)

This is one of those problems that, if you have the right insight in the beginning, takes very little time to figure out. However, if you're like most of us (me included), your first thought is to bring the number of passengers down to something manageable; i.e., under four.

So imagine there are only two passengers on an aircraft with two passenger seats. Passenger #1 goes onboard, picks a seat at random, and you must pick the other seat. There's no doubt that your chances of getting your assigned seat are one in two; i.e., the probability is exactly 1/2.

Ratcheting up the difficulty only a teeny bit, imagine the number of passengers (and assigned seats) to be three. A little more work quickly leads you to the same probability of 1/2 of finally getting your assigned seat. Ditto when the number of passengers is four.

Now let's take a big step and wonder if the probability is 1/2, no matter now big the number N of passengers is (as long as N is at least two). Here are all the boarding scenarios that allow you to sit in your own seat: First, passenger #1 sits in seat #1 with probability 1/N. In that case, each succeeding passenger sits in her/his assigned seat, and you sit in yours too. On the other hand, passenger #1 sits in seat #K > 1. After that, passengers #2 through K-1 sit in their assigned seats; whereupon passenger #K makes a random choice among seats #1 and those numbered > K. In effect, passenger #K is in the same position as was passenger #1; only the number of available seats is now smaller than N. This allows us to argue by induction.

So, for each K, at least 2 and no more than N-1, there is: first the probability of 1/N that passenger #1 sits in seat #K; second, the probability that you get to sit in your seat after all, once that happens. This latter probability is 1/2, by the inductiion hypothesis; hence the probability of you sitting in your pre-assigned seat is (1/N)+((N-2)/N)(1/2)=(2/2N)+((N-2)/2N)=N/2N=1/2. This establishes, via an induction argument on the number of passengers, that you have exactly a fifty-fifty chance (rather surprising to me) of getting your assigned seat after all the mixup.

The "quick" argument, after you have done all the experimental work, is this: First, either seat #1 is chosen before seat #N or it isn't. Each of these outcomes has probability 1/2. (Not entirely obvious to me at the outset, but hey.) Next, if seat #1 is chosen first, then you're assured of getting your pre-assigned seat. Hence, the probability of you getting your seat is 1/2. (Note: The only alternative to your getting your pre-assinged seat #N is to get seat #1.)