Fog Creek Software
Discussion Board




crazy guy on the airplane, yet a simpler solution

Brett van Swelm did it right, and Kevin Laws provided much simpler way of thinking. I've got even a simpler solution, which actually removes part of Kevin's construction from the scene, and it is very funny, IMHO.
1)What could be the number of the seat last passenger will occupy? It can be his own, it can be the crazy's guy. Can it be anything else -- say, number 45(we assume the crazy guy is not 45)? No. Why? Since this means, that the seat #45 was free all the time -- but in this case passenger 45 would take it, since it is his seat.
OK. So, the last guy can take only eaither his seat, or the crazy guy's.
2)Now let's look at the picture after crazy guy took somebody else's seat. Both his seat and last guy's seat are absolutely equal in the whole further experiment -- they both  belong to nobody(before the last guy enters). Thus -- they have exactly same chances in all possible scenarios.
So, because of their full symmetry in the problem -- we get 50/50 for them to meet the last guy.

Dmitri Krylov
Sunday, September 07, 2003

I'm not sure if I followed your argument for point number 2, and most of the old postings either tried to add up probabilities or argue recursively, but it's pretty easy to prove precisely by induction.

Obviously, if there are two seats, the crazy guy has a 50/50 chance of sitting in the wrong seat.

Now assume that for all planes of size 1..N-1 the last guy has a 50/50 chance of getting his own seat.  For the N-seat case, the crazy guy has a 1/N chance of sitting in his own seat (seat #1), in which case the last guy would get his seat, and a 1/N chance of sitting in the last seat, in which the last guy would not.  In all other cases, the crazy guy goes to seat M, and you can then consider the Mth guy to be the first crazy guy on a plane with N-(M-1) seats.  Since we know (by the induction hypothesis) that all those cases will have a 50/50 chance of leaving the last seat unoccupied, the probability for the N-seat case is 1/N (crazy guy lands in first seat) + N-2/N * 1/2 = 1/2.

Andrew

Andrew Certain
Sunday, October 05, 2003

I believe that the answer is the following. It is followed by reasoning. Please correct me if I'm wrong.

Probability of Nth seat being occupied is:
P = (2^(N-2) -1)/(2^(N-1)-1)

(Answer to the actual question would then be 1-P)

I did it the following way.

P = (Count of favorable combinations C)/(Count of all possible combinations, as constrained by the problem T)

T = Sigma T(i) , where 2<=i<=N, where T(i) is the count of possible combinations when the crazy guy is in seat i.

Similarly,

C = Sigma C(i), where 2<=i<=(N-1), where C(i) is the count of combinations when Nth guy is occupying Nth place.

Running manual calculations,

T(N) = 1
T(N-1) = 2 [Expl: When the crazy guy goes and sits in (N-1)th position, (N-1)st guy can either sit in the Nth pos or in 1st pos, giving two possible combinations of arrangement.]
T(N-2) = 4

Hence, T = Sigma(Ti) = (2^(N-1)-1) .

Similarly, we calculate C and eventually drive to the above formula.

I have verified the answer by manual work for N =3, 4 ,5 ... and it seems to be working.

Soham Mehta
Monday, October 20, 2003

Your calculation is based on the assumption that crazy guy never seats on his own seat (seat no. 1). This is not what problem says. Read Carefully: "the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy". Crazy guy ignores his seat #...he will never look at his seat number and randomly choose his seat (There is a 1/N probability that he might choose his own seat).

Your answer is perhaps correct in the case the problem says - 1st guy knows his number and decides not to sit on his own seat...in that case he will always pick up somebody else's seat (with 1/N-1 probability).

It depends on how you interpret "Ignore" word in problem statement. Does ignore means knowing the seat number and decide NOT to occupy his own seat at all OR does ignore means not caring/knowing at all what his seat number is and randomly pick the seat. Answer would be different in both cases. My interpretation would be the second one...and so the answer is 1/2.

Harsh Shah
Monday, October 20, 2003

Case 1:  The crazy guy sits in his own seat (1 time out of 100).  Then everyone else will sit in their own seat.  The 100th person will sit in his own seat.

Case 2:  The crazy guy sits in a seat that is not his own (99 times out of 100).  He is sitting in the seat of someone who is not yet on the plane.  The 2nd person gets on and sits in his own seat if it is available leaving only the crazy person in the seat of someone who is not yet on the plane.  Or, if the crazy person was in the 2nd person's seat, the 2nd person will choose a random seat and will become the one person on the plane in a seat that belongs to someone not yet on the plane. (The crazy guy is in a seat belonging to someone who is now ON the plane).  This process repeats as each additional person gets on.  There will always be exactly one person who is in the seat of someone who is not yet on the plane.  When there is only one person left to get on the plane, someone MUST be in his seat.  In Case 2, the 100th person will never be able to sit in his seat.

Case 1, the only case where the 100th person sits in his own seat, occurs only 1% of the time so the probability is 1%. 

Joanna Deitch
Monday, November 10, 2003

Joanna, consider a case you haven't described:

Crazy guy sits in seat 2; passenger 2, finding his seat taken, sits in seat 1. Everyone else gets on as scheduled.

Ham Fisted
Friday, November 14, 2003

*  Recent Topics

*  Fog Creek Home