Fog Creek Software
Discussion Board

crazy guy on the airplane

I have calculated the answer to be equal to 1/2.
The probability that the 100th person will get his own seat is 1/2.

explaination :
( A person with seat number i, will be refered to at the ith person  )

Consider and array of size 100, A[1] to A[100]
A[i] denotes the person on seat i.

Suppose 1 sat on ith seat. For all people between 1 and i, they sit on their proper seats. Now i sits on either 1 or something great than i, say j. Now j sits on k and eventually someone sits on 1.

This makes a cycle, in which starting point is 1, and the ending point is also 1. All other elements in that cycle are in increasing order.

Note that if the cycle contains 100, it means 100 sat on 1's seat.
If the cycle does not contain 100, it means 100 got his own seat.

A be the set of cycles which do not have 100 in it
B be a set of cycles which do have 100 in it

Cycle of A can be written as  ( 1, incresing sequence from 2 to 99, 1 )
Cycle of B can be written as  ( 1, incresing sequence from 2 to 99, 100, 1 )

Thus we see that number of elements in A is same as in B.

Thus number of cases in which A gets his seat is same as number of cases in which he does not get his own seat.

Hence probability is 1/2

Pankaj Gupta
Tuesday, April 23, 2002

I get 1/2 too - but a less mathsy proof

Seat 2 will always be full - either Mr 2 sits in it, or it was filled (by Mr1) and Mr 2 sat somewhere else.  Same is true for seat 3, either Mr 3 sits there or someone else already has  etc. for 4,5 ...

So Mr 100 arrives, seats 2-99 are full, either someone is in his seat, or someone is in seat 1 and so seat 100 is empty.

At anytime, anyone except Mr 100 who was choosing between seats 1 and 100 has the same chance of choosing either - so it's 50% chance seat 100 is free, 50% seat 1 is free.

Good puzzle

NB - this depends on the order of boarding - the problem space is more interesting if there is a more random selection of seats e.g. what if each person has a 10% chance of being crazy, and people board in a random order ? What if they board in simultaneous groups ?

jim dallas
Friday, April 26, 2002

I also get 50%, but not the same way.

Two things matter in this problem:  the number of empty seats when the passenger boards, and the fact that out of all occupied seats only one could possibly belong to him or her.

So, generalize to the simplest case, which is two seats and two passengers.  The crazy passenger doesn't care where he sits, so he has a .5 probability of sitting in either seat.  The second passenger has a 1.0 probability of getting *a* seat, but only a .5 probability of getting his *assigned* seat, where .5 = (1 seat available / 2 seat population that definitely contains his assigned seat).

Take this out to three passengers.  The second passenger has a .66 probability of getting his assigned seat (2 seats available / 2 empty seats + the 1 occupied seat that *could* be assigned to him).  The third passenger has a .5 probability, same as with the two passenger case.

So, to summarize:

N = Number of seats on the plane
P = Passenger number (not including crazy passenger #1)
X = Likelihood of getting seat

X = (N - P + 1) / (N - P + 2)

When N = P (which is the case for the last passenger), X = .5.

Trebor Nessumsar
Saturday, April 27, 2002

My solution seems to be more complex.
Situation. Let crazy guy sat at place number K. All passengers before K sat at their places. If he/she sit to place 1, all other passenger will sit at their own places, otherwise K-passenger sit at place L and situation repeats for passengers from K+1 to L.
K=99. Probability that 99-passenger will sit on first place is 1/2. Let denote P2 as probability for 100-passenger to sit on his own place in this case (2 - number of empty places).
K=98. Three places are empty (P3). One third that 98-passenger will sit on first place and same for place 99. P3 = 1/3 + 1/3*P2=1/3*(1+P2)
K=97. P4=1/4*(1+P2+P3)
K=n. Pn=1/n*(1+P2+P3+...+P(n-1))
Let show that Pn=1/2 using math induction method.
For n=2 P2=1/2. Let P(n-1)=1/2
Pn=1/n*(1+P2+P3+...+P(n-1))=1/n*(1+(n-2)*1/2)=1/n*(n*1/2) = 1/2.
Next step. All situations are independent. I.e. whether crazy guy sit on place k depends only on him and situations has no cross-references. So we can summarize probabilities.
Probability for situation K=99 is 1/100*P2, for situation K=n is 1/100*P(100-n+1)=1/100*P2. n is between 2 and 99. So we have 98 similar situations when crazy guy sits on other person place but passenger #100 still have chance to sit on his own place (99-2+1). K=100 is bad situation, P1=0.
All 98 situations can be calculated by formula Pn.
So summary probability is P(sum)=98*1/100*Pn=98/200.
One additional situation K=1 (let it be P100) is simplest one: crazy guy sits on place # 1. It cannot be calculated by Pn formula. But its probability is 1/100.

Michael Kolechkin
Sunday, May 12, 2002

Here's how I got 50% probability:

When the crazy guy sits down, there are three relevant possibilities:

A) he sits in seat 100.  In this case, guy 100 is guaranteed NOT to get his seat.

B) he sits in seat 1.  In this case, guy 100 is guaranteed to get his seat (since everyone from then on sits in their proper seat).

C) he sits somewhere else.  This essentially just repeats the experiment by forcing some other passenger to sit in a random seat.

So A and B happen with equal probability.  If C happens, then some other passenger (the one who's seat is taken) has to take a random seat, and again, there are the same three relavent possibilities as above.

So this is just a repeating random experiment, that eventually ends in state A or B.  Since A and B are equally likely in each repetition of the experiment, common sense (and I guess some theorem of probability theory) tells us that the whole repeating experiment will end at A or B with equal probability.

Billy Martin
Saturday, May 18, 2002

Isnt this as straightforward as - the 100th guy gets his seat or does not get his seat.  The seat is occupied by somebody or not occupied.  a 50-50 chance!

Saturday, May 25, 2002

*  Recent Topics

*  Fog Creek Home