techInterview Discussion

A part of answers to technical interview questions.

Your host: Michael Pryor

Crazy Guy on the Airplane: A Different Solution

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.
Peter Zion Send private email
Friday, July 04, 2008
Nice! Looks right to me.
Sunday, July 06, 2008
Well, except that under those rules the crazy guy would always be forced into his own seat, if the last guy in line behaves like all the other non-crazy folks...
aph Send private email
Sunday, July 06, 2008
aph, I suggest you read the definition of "middle guy" again.
Tuesday, July 08, 2008
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:
aph Send private email
Tuesday, July 08, 2008
psst... your overlooking the 1:100 odds that the crazy guy will randomly sit in his assigned seat... otherwise, yes 50/50
Mort Send private email
Friday, August 29, 2008

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz