
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 299 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 Kpassenger sit at place L and situation repeats for passengers from K+1 to L.
Solution.
K=99. Probability that 99passenger will sit on first place is 1/2. Let denote P2 as probability for 100passenger to sit on his own place in this case (2  number of empty places).
K=98. Three places are empty (P3). One third that 98passenger 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(n1))
Let show that Pn=1/2 using math induction method.
For n=2 P2=1/2. Let P(n1)=1/2
Pn=1/n*(1+P2+P3+...+P(n1))=1/n*(1+(n2)*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 crossreferences. So we can summarize probabilities.
Probability for situation K=99 is 1/100*P2, for situation K=n is 1/100*P(100n+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 (992+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.
P=98/200+1/100=1/2.
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 5050 chance!
deepeddie
Saturday, May 25, 2002
Recent Topics
Fog Creek Home
