Qua locus

Keeping both eyes on the long game.

Because economy class is bonkers…


This blog has been split in three and all content moved to the new blogs – Qua Locus LifeQua Locus Tech and Qua Locus Puzzle – comments are disabled here.

This post describes yet another logic puzzle. YANL? I love logic puzzles 🙂

100 passengers are lined up, ready to board their flight home. Each has a boarding pass for one of the 100 seats on the plane, and in a normal situation everyone would board and sit in their assigned seat. On this flight though the first passenger is crazy, doesn’t even read his boarding pass and sits in a randomly selected seat. Each passenger after him either sits in their assigned seat (if it’s free) or picks one at random.

What is the probability that the 100th passenger sits in his assigned seat?

Advertisements

Written by CGF

November 22, 02012 at 16:21

Posted in Puzzles

Tagged with

One Response

Subscribe to comments with RSS.

  1. SPOILER ALERT: Solution is described in this comment!

    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .

    The answer is 50%, and it’s 50% regardless of the size of the plane. This can be shown in a number of ways, here are two:

    Using informal intuition first: Consider the case of a plane with n=2 seats. P1 is going to sit randomly, so there is a 50% chance he sits in seat Sn and a 50% chance he sits in S1. Therefore answer = 50%. Next, consider the situation with n=3 seats. P1 has a 1/3 chance of sitting in S1, a 1/3 chance of sitting in S2 and a 1/3 chance of sitting in S3. If he sits in S3 then P3 does not get his seat, however if he sits in seat S2 then there is a 50% chance P3 gets to sit in S3 (as P2 picks randomly from amongst S1 and S3). Since 1/3 + (1/3 * 50%) = 50%, the answer is again 50%. This answer can be built up similarly, but more long-windedly, for all larger n (including n=100).

    Several observations help structure the second approach:
    * As soon as someone sits in S1 all future passengers will sit in the correct seat, including P100
    * As soon as someone sits in S100 it does not matter where all future passengers sit, P100 will not sit in S100
    * Apart from P1 and P100, the only passengers we have to consider are those which cannot sit in their own seats (other passengers will sit in their own seat and will not change whether P100 can sit in S100)

    With these observations in mind, first consider P1. If they sit in S2..S99 then the outcome is still to be determined and we must consider later passengers. Otherwise if they sit in S1 or S100 then the probability that P100 can sit in S100 is 50%.

    Next consider Pi, and assume that Si is occupied. Like P1 if they sit in any of the seats S2..S99 then the outcome is still to be determined and we must consider later passengers. Otherwise if they sit in one of the seats in the set then the probability that P100 can sit in S100 is 50%.

    This shows that the probability P100 can sit in S100 is 50%, although it might not be totally clear straight away, so a couple more illustrations might help:

    Consider P99, and assume that S99 is occupied but that the outcome is not determined. Because they are passenger 99, 98 of the seats must be occupied so only S1 and S100 could be unoccupied. Therefore there is a 50% chance that they will sit in S100 and there is a 50% chance that P100 will sit in S100.

    Similarly, consider P98, and assume that S98 is occupied. If P98 sits in S99 then the situation just discussed in the above paragraph occurs, and the probability that P100 sits in S100 is 50%. On the other hand, if P98 doesn’t sit in the set of seats S2..S99 then they must sit in either S1 or S100, P99 will sit in S99, and P100 has a 50% chance of sitting in S100 (i.e. if P98 sits in S1).

    Finally, consider P2, and assume that P1 sat in S2. In this case P2 is just Pi from four paragraphs above. Either they sit in one of the seats S3..S99, postponing determination of the outcome to a later passenger, or they sit in one of the seats in the set , in which case there is a 50% chance that P100 sits in S100.

    To summarise: P1 and each passenger P2..P98 that cannot sit in their own seat either postpones determination of the outcome to a later passenger who also cannot sit in their own seat or determines that P100 can sit in S100 with 50% probability. If the outcome is not determined for P99 then there is a 50% chance that P100 can sit in S100. Therefore the probability that P100 can sit in S100 is 50%.

    Christo Fogelberg

    November 29, 02012 at 07:52


Comments are closed.

%d bloggers like this: