Visit our sponsor Granny's Eggs  
Search: Go
Home
Microsoft Interview Process
HR Questions
Technical Questions
Puzzles/Riddles
Resume Tips and Template
Discuss
Question to Interviewer
Interview Tips
Term Of Use
Site Feedback
Login
Register


Crazy Guy On The Airplane

A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.)

Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. if it is occupied, they will then find a free seat to sit in, at random.
What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

 

I haven't written up a solution for this yet, but smarter people than me can put the solution in comment section

Comments:

Solution
By psyang on Tuesday, August 29, 2006 (UMST)

Took me about 10 minutes to work this out. Cool puzzle.

 

Let P(i) = probability that the ith person after the crazy guy loses their seat. What we want to know is P(99). 

P(1) = 1/100 (the crazy guy picks seat 1). Notice that it is not 1/99 - the crazy guy could pick his own seat since he selects purely by random. 

P(2) = 1/100 (crazy guy picks his seat) + P(1)*1/99 (crazy guy picks the first guy's seat, and the first guy picks the second guy's seat).

Following this sequence, we get the following recursive relationship: 

P(n) = P(n-1)(1/(101-n))

If we start to work this relationship out, we get a surprising answer:

P(1) = 1/100

P(2) = 1/99

P(3) = 1/98

and, more generally,

P(n) = 1/(101-n) ( for n<100)

Thus, P(99) = 1/(101-99) = 1/2

 

-Peter

100 pepole on an airplane
By mnause on Saturday, October 07, 2006 (UMST)
This is not a riddle or a question of probability. It is a simple question of common sense. If you're trying to be logical you must consider all factors, like the , "Hey nutso, get your ass outa my seat. Your ticket says seat 18, go find it," factor. What I mean is that you have to assume that the crazy guy has seat one or he wouldn't be first in line. He's crazy, not stupid, neither are the fellow passengers, who would line up correctly and go find their seats. But for argument's sake, let's just say he randomly jumps in the front of the line holding the ticket for seat number 22 and sits in seat 57. All the other passengers, instead of following their seat numbers begin sitting down at the first seat and follow on in order. The first 21 would be in the right seats. The next 36 (including the crazy guy) would not. At seat 58, order would be restored and the last 43 people would be in their correct seats. So, the only way the last guy's seat gets screwed up is if 'Nutso' randomly jumped in it to begin with. 1 in 100 chancwes right. So the probability is that he/she will end up in the correct seat is 99%.

Whaaaattt?!?!?!
By mnause on Saturday, October 07, 2006 (UMST)
Hello Peter, wake up you're dreaming. You have taken to complicated an approach to this. Ten minutes? Are you the crazy guy in the riddle? Five seconds at best.

Sorry Mnause
By Celton on Thursday, December 07, 2006 (UMST)
The puzzle specifically states that the other passengers randomly choose a seat if their seat is taken, they don't "follow on in order", as you put it.  Peter's solution is correct.

100 pepole on an airplane
By matyagi on Monday, January 08, 2007 (UMST)

I think, in such problems we should start from end. Let the 100th passenger sit on 100th seat no.. Now we can make 99 other passangers sit in 99! ways. Therefore the probabilty of 100th passenger sitting on correct seat no. is 99!/100! which comes out to be 0.001

 

Thoughts?

--Manoj

New Articles
  • Program the Fib Sequence without recursion
    •
    Everyone learns how to do recursion with the Fibonacci sequence in Programming 101. Do it programmatically without recursion.

  • Implement and test a memcpy function
    Given a function header (in fact an out-of context function call):
    memcpy(src, dst, size)
    Write an implementation and test cases.
    Be sure to ask additional questions on what exactly the function does and the range of arguments as well.



  • Implement an allocator
    Implement a memory allocator, i.e. malloc function, free function and all data structures, needed for that.

    •  
    Most Popular Articles
  • Crazy Guy On The Airplane
    •
    A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight.

  • Question: Tell me about yourself.
    Many candidates, unprepared for the question, skewer themselves by rambling, recapping their life story, delving into ancient work history or personal matters.

  • What are your greatest weaknesses
    Beware - this is an eliminator question, designed to shorten the candidate list. Any admission of a weakness or fault will earn you an “A” for honesty, but an “F” for the interview.

    •  




    •