A Variation on a Theme
Dave
to a seat, numbered 1-100. They are in line in random order. The
first passenger is crazy and will sit in a random seat. Each
passenger after that will enter the plane in their random order. If
his assigned seat is vacant, he will take it. If not, he will take
the nearest open seat. If two seats equally far from their seat are
both available, he will take the one further to the back. For
instance, if a passenger is assigned to seat 40, but seat 40 is taken,
he will scan for an open seat in this order: 41, 39, 42, 38, 43, 37,
etc.
What is the probability that the last passenger gets his assigned
seat?
dgates
I know I've heard a variation on this puzzle -- the "original"
version, but it didn't explain the logic by which people will pick
their replacement seats. (By the way, this must be one long, thin
plane -- 100 rows of seats, each containing only one seat??)
I don't see how to work out any complexities added by the
alternate-seat-picking algorithm, so I think I'll solve as though each
guy takes a random seat.
I'm actually not sure what question was asked in the "original," but I
don't think it was "Will the last guy get his seat?"
Let's say the first guy actually had seat #22. It appears that the
first guy has a 99% chance of throwing the plane into a state of
"chaos" (by taking a seat other than #22).
That chaos will then continue until one of the passengers finds
his/her seat snatched and takes seat #22 instead.
It looks like there are 99 possible passengers who might take seat
#22, and therefore a 99% chance that the last passenger will get his
assigned seat.
Since the first passenger picks randomly, and the other passengers
board in a random order, I think that randomness will overcome their
alternate-seat-picking algorithm.
Paul Hunter
I looked at a few simple cases (2 & 3 passengers) and ran a simulation
and it looks like the answer should be 1/2. After some ponderance,
here's why...
Let the seat the first passenger sat in be represented by the random
variable 'a', the seat he was supposed to sit in by 'b' and the last
passenger's seat by 'c'. Note that as soon as one of b or c is occupied
then the remaining passengers will sit in their assigned seats with the
last passenger sitting in whichever of b or c is unoccupied. Let sigma
be the random variable denoting the permutation of the remaining
passengers. So an event in the (uniform) probability space is going to
be of the form (a=a',b=b',c=c',sigma=sigma') (or (a',b',c',sigma') for
short). But for every successful event (a',b',c',sigma') where b is
occupied before c, there is an unsuccessful event: (a',c',b',sigma')
where c is occupied before b and vice-versa. As each has the same
probability of occurring the probability that the last passenger gets
his seat is exactly 1/2. Note that this is independent of the
seat-picking algorithm (as long as it is determined for every value of
sigma).
With the given seat picking algorithm we can identify some of the
successful events, namely (a',b',c', sigma') where b' is between a' & c'
(or equal to a'). Symmetrically, unsuccessful events are where c' is
between a' & b' (or equal to a') - this is because the "chaos" "spreads
out" from seat a until it hits either b or c. When a' is between b'&c'
then the success depends on sigma'
Mark Tilford
Answer is:
50%
Of the n*(n!) ways to (order the n passengers and for the first
passenger to choose a seat), pair two iff they differ only in where the
first person and last person are assigned. Everyone will sit in the
exact same seats. Consider the first person X to sit in the assigned
seat of either the first person or the last person. If he sits in the
first person's seat, everyone after that (in particular, the last
person) sits in their correct seat; if he sits in the last person's
seat, the last person obviously won't get the right seat. Since in one
member of the pair, he sits in the first person's seat, and in the
other, he sits in the last person's seat, the last person gets his
correct seat in exactly half of all possibilities.
dgates
Dang. This WAS the original puzzle! I remembered the original answer
being 50%, and it coming down to a whether each passenger sits in one
of two seats, therefore 50-50. But I still got it wrong when
confronted with the new, confusing seating algorithm! :-o