Fog Creek Software
Discussion Board




crazy guy on the airplane

the crazy person's seat is 1, last person's is 100

the key axiom is this:

whenever a passenger number n sits on seat 1 or 100,
all passengers > n will sit  in their proper seat

consider passenger 99, when he gets on the plane.

there are two possibilities

1. his seat is taken

in which case there are two open seats, 1 and 100
so there is a 1/2 chance that he takes seat 1 and
leaves 100 free

2. his seat is not taken

this means that someone has sat in either seat
1 or 100 before him, otherwise his seat would be taken.

so, that someone had equal chance of sitting in 1 or 100
meaning there is 1/2 chance they sat in 1
leaving 100 free.

either way, 1 or 2, there is a 1/2 chance that seat 100
is free when passenger 100 gets on.

1/2

Cheradenine Zakalwe
Thursday, June 06, 2002

I don't agree. I think there is a 1/100 chance that the crazy guy sits in his own seat and then everything works.

99/100 times the crazy guy picks somebody else's seat. That person (no matter what number they are) will ALWAYS have to pick somebody else's seat. Eventually this must trickle back to person 100 and his seat would have been taken by another.

So I think it's 1%. But something doesn't sit quite right about that...

Jason Wood
Tuesday, July 02, 2002

As soon as I posted this, I realized what was wrong. There is a (always changing) probability that a person randomly sits in seat #1, and everything returns to normal for the remaining passengers.

So in the 99/100 case, there is a 50/50 chance that passenger #99 picks either vacant seat, this is true. But we are in no way guaranteed that seat #100 is still free. Each person before him also had a 1/X chance of picking seat #100.

So maybe it is 99/100 * 98/99 * 97/98 ... * 1/2 is the probability that seat #100 is vacant.

I'm not entirely comfortable with that though.

Jason Wood
Tuesday, July 02, 2002

if seat 100 was taken by someone before
passenger 99, then seat 99 is free.

(in general, if anyone takes the wrong seat n,
then all passengers < n will sit in their
proper seat)

Cheradenine Zakalwe
Wednesday, July 03, 2002

Person 100's chance of getting his proper seat is (chance that #99 didn't take it)*(chance that #98 didn't take it)*(chance that #97 didn't take it)*...*(99/100 chance that Crazy Man didn't take it).  Call this F{99}*F{98}*F{97}*...*F{1}.

When person 99 gets on the plane, there are two seats left.  There is a chance, P{99}, that his Proper seat is one of them, in which case he takes it.  Otherwise (1-P{99}), he picks one of the two at random.  So, chance that person 99 didn't take seat 100: F{99}=P{99}+[(1/2)*(1-P{99})].
Likewise, person 98 sees three empty seats: if none are his, he has a 2/3 chance of choosing a seat other than 100:(2/3)*(1-P{98}).  So F{98}=P{98}+[(2/3)*(1-P{98})]In general, chance that person N didn't take seat #100 is
F{N}=P{N}+[((100-N)/(101-N))*(1-P{N})].

For person #1, Crazy Man, there is 1/100 chance he sits in his own seat; otherwise, he has a 98/99 chance of picking a seat other than #100.  So his chance of not taking #100, F{1}, is (1/100)+[(98/99)*(99/100)].

Now, CM's chance of not taking seat #2 is the same as the chance of not taking seat #100.  So P{2}=F{1}.  Person 2's chance of not taking seat #100 is then F{2}=P{2}+[(98/99)*(1-P{2})].

What about person 3?  The chance that CM didn't take his seat is the same as the chance that CM didn't take seat #100, F{1}.  The chance that passenger 2 didn't take 3's seat is the same as the chance that 2 didn't take seat #100, F{2}.  so P{3}=F{1}*F{2}.

Likewise P{4}=F{1}*F{2}*F{3}=P{3}*F{3}.  In general, P{N}=P{N-1}*F{N-1}. 

At about this point my calculus skills fail me, and I plug the formulas into a spreadsheet, getting a result of P{100}= about 0.453597

David Ackermann
Friday, July 05, 2002

*  Recent Topics

*  Fog Creek Home