Classic puzzle:
An airplane has 100 passengers. But the very first one to get on is missing his ticket! He just takes a random seat, and refuses to move from that spot.
The rest of the passengers board the plane one by one. Each passenger takes the correct seat, unless it's already taken. If their seat is already taken, they sit in a random seat, and refuse to move.
What's the probability that the last passenger gets the correct seat?
(Hint: First try to consider an airplane with 2 or 3 passengers)
Extra Challenge:
It turns out that the first passenger isn't isn't really confused, he's malicious! He knows where he's supposed to sit, and intentionally sits anywhere but there. What's the probability that the last passenger gets the correct seat?
see the solution
Saturday, May 7, 2011
Subscribe to:
Post Comments (Atom)
5 comments:
Presumably the plane has only 100 passenger seats.
With 2 passengers, the random guy will take his correct seat half the time, so the probability of the last passenger getting his seat is 1/2.
With 3 passengers, 1/3 of the time the random guy will take his correct seat (and last guy will get his) and 1/3 of the time he'll take the last guy's seat (and the last guy won't). So far it's 50:50.
If the random guy takes the seat of passenger #2, then passenger #2 can either take the seat of the random guy or that of the last guy. These are the same choices that the random guy has with only 2 passangers and we have already seen that the odds are 50:50 for this scenario. So the probability is again 1/2.
With 4 passengers, once you eliminate the random guy sitting in either his own seat or that of the last guy, it becomes analogous to the 3 passenger scenario. Probability is again 1/2.
So the probability of the last passenger being able to take his correct seat when there are 100 passengers (or any number greater than 1) is 1/2.
For the Extra Challenge:
If the random guy is now malicious guy, he'll never take his correct seat. Therefore with only 2 passengers, the last guy has no chance of getting his seat.
With 3 passengers, 1/2 of the time the malicious guy will take the last passenger's seat (so, no chance for the last guy), and 1/2 of the time he'll take passenger #2's seat. If this happens, there is a 50% chance that #2 will sit in the last guy's seat.
Therefore his total probability is 0 + (1/2 * 1/2) = 1/4.
Similarly (without writing it all out) it can be shown that with 4 passengers, the probability of the last guy getting his seat is 0 + (1/2 * 1/3) + (1/2 * 1/3) = (1/2 * 1/3)* 2 = 1/3; and with 5 passengers it is (1/2 * 1/4)* 3 = 3/8
General formula is (n-2) / (2(n-1)) where n = number of passengers = number of seats. As n gets larger and larger, the probability gets closer to 1/2 (that of the first problem). This makes sense as it must be less than 1/2 since the most favouring possibility (#1 choosing his correct seat) is not permitted. It also makes sense that the probability approaches that of before as the effects of the first passenger's maliciousness is "diluted" amongst more and more other passengers.
So, for 100 passengers with a malicious passenger #1, the probability of the last passenger getting his correct seat is (100-2)/2(100-1) = 98/198 ~ 49.5%
Good problem and extension btw!
Congratulations, you got it!
There's also another way to prove it without induction.
If you're referring to the first problem, I obviously could have tried to work out the cascading probabilities for each of the 100 seats but I suspect you have something more elegant in mind.
Post a Comment