Crazy guy on the plane
Answer: The jumping stops if someone sits on the crazy man's seat before the 100th persons, hence, the 100th will sit in his/her seat for sure then. Similarly, if anyone sits on the 100th passengers seat at any point, then he/she won't get to sit his/her seat for sure. If at any point someone picks a random seat other than #1 or #100, then the jumping is postponed till that seat number is reached. At any jumping point there is a equal probability that seats #1 or #100 will be chosen (other choices will just delay the problem till later down the line). By symmetry, the probability of the 100th passenger sitting in their seat is 50-50, since at all jump points there's an equal probability of choosing seats #1 or 100.
Monday, December 13, 2004
You've got it right. Let me simplify the language a bit:
If any passenger <100 randomly selects seat 1, then each successive passenger can sit in his/her assigned seat including passenger 100.
If any passenger <100 randomly selects seat 100, then passenger 100 is forced to choose the only other remaining seat.
For each passenger (who is forced to choose randomly), the chance of choosing 1 and 100 is equal.
(The EXACT probability depends on the number of other remaining seats, but in each case the chance of choosing 1 and 100 is the same. 1/100 and 1/100 for the 1st passenger, 1/40 and 1/40 for the 60th passenger)
Each choice that doesn't choose seat 1 or 100 simply defers the final decision to a later passenger.
Therefore the chance of passenger 100 getting his own seat is 50%.
I had a nice proof by induction in a previous thread, but that thread has apparently been pruned.
Tuesday, December 14, 2004
Fog Creek Home