###
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.)