## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
Here's a different solution for the "Crazy Guy on the Airplane" problem than what' I've seen so far. It does not involve induction, at least not an induction on probabilities.
First, we will refer to passengers two through 99 as the middle guys and passenger 100 as the last guy. Change the rules very slightly: when a middle guy finds that his seat is occupied, instead of himself making a random choice among the remaining seats he forces the person in his seat to relinquish it to him and to make the same random choice among the remaining seats as the middle guy would have made. With this change, only the crazy guy ever makes random choices, and the random choices that are made are identical to those made according the original rules; thus the probability of the last guy eventually finding his seat free is the same. With the new rules, the crazy guy is uniformly choosing a seat, but if he chooses a middle guy seat it is effectively removed from the plane and he is forced to choose again. Thus he is effectively choosing uniformly between his own and the last guy's seat, so the probability that he chooses each is 1/2, the same probability that the last guy's seat is free when he arrives. Another way of looking at it is that in this new formulation the number of middle guys is immaterial, therefore the result for 98 middle guys is the same as the result for 0 middle guys, which is clearly 1/2.
LLRB, I read it. Just commenting that the last guy must act differently from the others, which the post does not explicitly mention. The meaning is clear of course - it's essentially the same thinking as, for example, this answer from the archives:
http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=899 |

Powered by FogBugz