Monday, June 6, 2011

Solution to the confused passenger

See the original puzzle

This puzzle can be solved by induction.  First consider the 2-passenger case, and then see what happens when we increment the number of passengers.  You will find that no matter how many passengers there are, there is always a 50% chance that the last passenger gets the correct seat.

However, there's another way to solve it.  Do like physicists do: ignore all details of the problem and just consider the symmetries.

Let's number all the passengers from 1 to 100 in the order that they board.  By the time passenger 100 boards, seats 2-99 are guaranteed to be filled.  Among the seats 1 and 100, exactly one is filled. But none of the passengers 1 to 99 make any distinction between seats 1 and 100.  (In other words, seats 1 and 100 are symmetric with respect to switching.)  Therefore, seat 1 and 100 are equally likely to be filled, each with a 50% chance.

The malicious passenger

1% of the time, the confused passenger sits in his own seat, which allows the final passenger to get the correct seat.  The other 99% of the time, the confused passenger acts exactly like the malicious passenger.  Therefore, we get the following equation:

0.5 = 0.01 * 1 + 0.99 * X

...where X is the probability that the final passenger gets the correct seat if the first passenger is malicious.

Solving for X, the probability is 49/99