Fog Creek Software
Discussion Board




The crazy passenger

This is a fairly difficult problem to solve properly, though I guess the answer can be arrived at more easily. Found this one on a russian logic questions site and tried to translate is as best as I could:

http://www.flooble.com/perplexus/show.php?pid=14

levik
Friday, April 19, 2002

don't forget, my puzzle well has run dry so if you come up with any good ones you think should be on the site, let me know...

Michael H. Pryor
Friday, April 19, 2002

My guess is 0.5  . At any time, there can be at most only one person in the wrong seat. Every person who chooses to take a seat at random can only finish the game by choosing seat 1 or 100, the rest are irrelevant. The changes of choosing 1 and 100 are equal, giving a probability of 1/2

Paul Viney

Paul Viney
Friday, April 19, 2002

my guess is 99% likely that the last guy sits in his seat

Michael H. Pryor
Friday, April 19, 2002

The probability that the last guy gets to sit in his seat is 1:100.  If the crazy guy sits in his correct seat then that is the only chance the last guy will have to sit in his own seat.

Erik
Friday, April 19, 2002

This isn't really an answer except to show that you other people haven't considered this very well.

Every passenger that can't find his seat and the crazy dude has a 1/remaining seats chance to let the 100th guy get his seat. They also has a 1/remaining seats chance to take the 100th guys seat. Every passenger also has (remaining seats-2)/remaining seats chance to reduce the number of seats by some random number of (remaining seats-2) because the probability is only tested for the people that can't find their seat and of course that first crazy dude.

CrashCodes
Friday, April 19, 2002

Am I the only one losing my mind about this question?

So I take the first chance that the crazy dude takes his own seat and add it to the product of the remaining chances that he takes a seat thats not seat 100 and the chance the next guy has of picking seat number 1.

1/100 + 
(98/100 * 1/99) +
(97/99 * 1/98) +
(96/98 * 1/97)...

This can't be right because what happens when the iteration gets to 0/2 * 1/2?

Every passenger has a chance to pass/fail/iterate
Suppose the 1st and 100th seat arent taken and passenger 99s turn to take a seat but its taken. he has 1:2 chance to take seat 1 which will lead to the 100th dude getting his correct seat. He has 1:2 chances to take the 100th dude's seat.

Okay I've thought enough about this too much already. Regardless of how many possible iterations are still available, there is always an equal chance to succeed and fail.

I'm going to have to say 1:2 is the probability of passenger 100 getting his seat.

CrashCodes
Friday, April 19, 2002

Well, the answer <b>IS</b> 1/2. I posted a pretty mathematical solution on perplexus (linked above). Not sure if it's the only correct solution. Maybe this can be solved with logic as well.

levik
Friday, April 19, 2002

the answer is 1/2.  here's how:

let p(x) denote the probability that the xth passenger finds his/her seat occupied when coming on board the plane.

when the first person gets on board, his seat is definitely NOT occupied.  so...

p(1) = 0

the second person will find his seat occupied if the first guy took it, and the probability of that is 1/100.  so ...

p(2) = 1/100

the third person will find his seat occupied if EITHER the first guy occupied it OR the second guy occupied it.  so ...

p(3) = 1/100 + p(2).1/99

arguing similarly, let's p(4) and p(5):

p(4) = 1/100 + p(2).1/99 + p(3).1/98
p(5) = 1/100 + p(2).1/99 + p(3).1/98 + p(4).1/97

you should now see a pattern emerging:

p(2) = 1/100
p(3) = p(2) + p(2).1/99
p(4) = p(3) + p(3).1/98
p(5) = p(4) + p(4).1/97
....
....
p(x) = p(x-1) + p(x-1).1/(100-x+2)
....
....
p(100) = p(99) + p(99).1/2

infact, it's easy to see why we get this pattern.  think about what happens when person 'x' boards the plane.  that depends on what happened when the (x-1)th person boarded the plane.  EITHER the xth seat was already occupied OR the (x-1)th person occupied the xth seat because the (x-1)th seat was taken. 

we know that the probability that the (x-1)th seat was occupied when person 'x-1' got on board is p(x-1).  THE KEY IS to realize that the probability that the xth seat was occupied at that time is also, infact, p(x-1).  Why?  because every occupied seat had the same likelihood of getting picked (because people chose their seats at random if their seats were taken).  if we add the two probability in the EITHER/OR case in the preceding paragraph, we get the formula:

p(x) = p(x-1) + p(x-1).1/(100-x+2)

Anyway, the rest is easy.

Simplifying our final pattern, we get the following:

p(2) = (1/100)
p(3) = (100/99).p(2)
p(4) = (99/98).p(3)
p(5) = (98/97).p(4)
...
p(100) = (3/2).p(99)

since each probability is > 0, we can safely multiply all the terms on either side and we get:

p(2).p(3)...p(100) = (1/100)(100/99).(99/98).(98/97)...(3/2).p(2).p(3)...p(99)

canceling numerators & denominators on the right side and p(2).p(3)...p(99) on either side, we get:

p(100) = 1/2.

so, the probability that the 100th guy sits in his/her own seat = 1 - p(100) = 1/2.

i find it easier to solve such problems by induction.  this was a good one!

Vin
Saturday, April 20, 2002

I agree that the answer is 50% but arrived at this by a slightly different way.

If the crazy passenger picks seat 100 then passenger 100 has 0% chance of getting his/her seat :-) (and passengers 2-99 are all sat in the correct places)

If the crazy passenger picks seat 1 then passenger 100 has 100% chance of getting his/hear seat (and everyone is sat in the correct place.)

If the crazy passenger picks a seat from 2-99 then passenger 100 has a 50% chance of ending up with the right seat. Here are some examples to show this:

Crazy takes seat 99: Passengers 2-98 in correct seats. Passenger 99 finds his seat taken so chooses randomly from seats 1 (passenger 100 gets his seat) and 100 (passenger 100 is left with seat 1) with probability of 50% in either case.

Crazy takes seat 98: Passengers 2-97 in correct seats.
Passenger 98 chooses randomly from seats 1, 99 and 100 with probability 33%. If he chooses seat 1 this leaves 99 and 100 for the correct people. If he chooses 99 then after that there is a 50% chance as above. Total probability = 33% + (33% * 0.5) = 50%

Crazy takes seat 97: Passengers 2-96 in the correct places. Then 25% chance of passenger 97 taking seat 1, leaving the right seats for the remainder + (25% * 0.5, if passenger 97 takes seat 98) + (25% * 0.5, if passenger 97 takes seat 99) = 50%

etc. etc. (scribble down the trees for 96, 95.. to see the series continues)

Returning to the top level of the problem. Crazy chooses a seat at random with probabilty 0.01 for each seat so for the cases where passenger 1 chooses a seat between 2 and 99 we have 98 * 0.01 * 0.5 probability that passenger 100 gets the right seat = 0.49. Add the 0.01 chance that passenger 1 chooses seat 1 and you end up with 50%

Michael Josephson
Saturday, April 20, 2002

*  Recent Topics

*  Fog Creek Home