Fog Creek Software
Discussion Board




"Crazy guy on airplane" problem solution

This solution is general, ie: it works for any number of passengers greater than 1.

Let P(n) be the solution to the puzzle with n passengers, ie: the probability of passenger n getting his correct seat.

There is a 1/n chance that passenger 1 (the crazy passenger) takes seat 1. So passenger n gets his seat.

Similarily, there is a 1/n chance that passenger 1 takes seat 2. If this has happened, passenger 2 will take a seat at random. We can regard this as the whole problem again, with n-1 passengers, and passenger 2 being the crazy passenger. This works because the untaken seat 1 becomes the "correct" seat for passenger 2, ie: the seat that means everyone from then on gets to sit in the correct place.

If passenger 1 takes seat k, k>3;k<n, every passenger from 2 to k-1 will take the correct seat, leaving seat 1 open as the correct seat for passenger k, who becomes the crazy passenger in the P(n-k+1) problem.

And if passenger 1 takes seat n, this is of course hopeless.

So we end up with a relatively simple sequence:

P(n) = 1/n + P(n-1)/n + P(n-2)/n + ... + P(2)/n

Now:

P(2) = 1/2

P(3) = [1+(1/2)]/3 = 1/2

P(4) = [1+(1/2)+(1/2)]/4 = 1/2

Adding a half to the denominator and one to the nominator each time, one can see that this is going to stay 1/2, for any P(n).

So the answer for 100 passengers is 1/2, or 50%.

Brett van Swelm
Tuesday, June 03, 2003

A small correction. I inadvertently left out the case where k=3 in "If passenger 1 takes seat k, k>3;k<n".

It should read "If passenger 1 takes seat k, k>2;k<n"

Brett van Swelm
Tuesday, June 03, 2003

I havent done the math, but the solution I came up with was like this:

p(100th passanger sits in 100th seat)
= p(1st passanger not in 100th seat) + p(2nd passanger not chose 100th seat) + ..... and so on
= 99/100 + 98/99 + 97/98 + .......
= summation (for i = 2 to n) [(i-1)/i]

this should also work for any "n".  I should do this math  to see if these two solutions match up.

saurabh
Tuesday, June 03, 2003

The problem with the summation of 99/100 + 98/99 + ... + 4/3 + 3/2 is that it leads to a probability far greater than one (I think around about 94 point something).

The reason this happens is that the probabilities that are being summed are not mutually exclusive. For example, if passenger 1 takes seat 1 and passenger 2 takes seat 2, etc, this circumstance is included in both p(1st passenger not in 100th seat) and p(2nd passenger not in 100th seat). This circumstance is, in effect, summed more than once.

You could do it the other way round, and say the following:

p(100th passenger sits in 100th seat)
= 1 - p(1st passenger sits in 100th seat) - p(2nd passenger sits in 100th seat) - ... - p(99th passenger sits in 100th seat)

Brett van Swelm
Wednesday, June 04, 2003

The only way the correct seat will be left open is if the crazy dude took the correct seat so 1 out of 100

Binyomin
Wednesday, June 04, 2003

actually i'm wrong since any of the displaced people can sit in the first guys seat hmmmmmmmm.

Binyomin
Wednesday, June 04, 2003

Actually, Brett has it right though there is a much easier way to think about it than with the equations. This is completely generalizeable to any number of passengers/seats.

There are two possibilities for the crazy passenger.
1. He resolves the problem now: Either he chooses the crazy passenger's seat or sits in the last passenger's seat.
2. He doesn't resolve the problem now: He sits in some other passenger's seat.

If the passenger does #1, then he has a 50% chance of selecting the crazy person's seat (in which case the last passenger gets his own seat) and a 50% chance of sitting in the last passenger's seat (in which case the last passenger sits in the crazy person's seat).

If the passenger does #2, then you repeat the logic when the new passenger finds his seat occupied and seeks a new seat.

However, notice that regardless of how many times you repeat the process, whenever you do come to the resolution (somebody will eventually sit in one of the two seats -- even if it is the second to last passenger), there is always a 50% chance that the last passenger will have his own seat.

Thus, the answer is "50%".

-- Kevin

Kevin Laws
Tuesday, June 17, 2003

P.S.: The "aha!" in this problem is realizing that the problem ends when somebody either sits in the crazy person's seat (in which case every subsequent person sits in the correct seat) or in the last passenger's seat (in which case you guarantee that the last passenger will not sit in the correct seat). When put that way, it's obvious that no matter how many people you have, once the problem is resolved there is a 50% chance of either outcome.

Kevin Laws
Tuesday, June 17, 2003

Actually there is a flaw in Kevin's explanation...

If your scenario #1 occurs the chance that the newest passenger on the plane takes the crazy guys correct seat because he took someone else's is NOT 50%.  It would actually be 1/n where n = the number of empty seats left at that time when that person boards the plane.  ie. 35th person on the plane (if it was his seat the crazy guy took) has a 1/66 chance of choosing the crazy guy's assigned seat.

So I would have to agree that the equation explanation is the best to describe the outcome...unless someone has a verbal explanation for the equation version. 

Sorry to criticize when I cannot myself offer that layman's terms solution for the equations.

Andrew Harty
Sunday, July 06, 2003

Read carefully, there is no flaw.

The scenarios are definitions. Scenario #1 BY DEFINITION is when the passenger resolves the problem by choosing one of two seats: the 100th passenger's seat or the crazy person's seat. Whenever scenario #1 occurs, since there are only 2 seats, the chances of either one is 50%.

Choosing any other seat falls into scenario #2: repeat the problem.

You are (almost) correct that the chances of scenario #1 occuring are 2/n, where n is the number of free seats left, but that isn't relevant to solving the problem. Scenario #1 is guaranteed to happen eventually (even if you get to the 99th passenger without resolving the problem, there will only be 2 seats left -- the crazy person's seat and the 100th seat).

Therefore whenever the problem is resolved, it will always be 50% likely to be resolved such that the last person gets their own seat, and 50% that they won't.

Kevin Laws
Tuesday, July 08, 2003

Yet another look at it.
Each passenger k has a certain probability to have his seat taken. That is by Passenger 1 or any passenger y < k.
Let's denote it as P(k).
If his seat taken, Passenger k has (N-k+1) seats to choose from. (N=100). But we actually interested only in two:
seat #1 which guranatee #100 to have his designated
seat. And seat #100 which "guarantee" that he lost his
seat. Any other seat x between k and N will be
taken into account in the probability function P(x) if x seat
is being taken.
Therefore, the chance of taking seat #100 is P(k)*1/(N-k+1)
But this is the exactly the chance of taking seat #1 instead.
So without having to solve P(k) but itself, one can see
that the partial probabilities of having #100 taken or not
adding up to the same value of 50%.

Aharon Tam
Sunday, July 13, 2003

P(First Person not taking the last seat) = 1/100
P(Second guy not taking the last seat) = 98/99
P(Third guy not taking the last seat) = 97/98
..........

Therefore itis 99/100 * 98/99 * 97/98 * .... 1/2

i.e. 99!/100! = 1 %

Howzzat !!!

PS: You do not have a right to argue against this answer.

bisi_bele_bath
Friday, July 25, 2003

We just care that the 100th seat is occupied by the 100th person. So first 99 people can be arranged on 99 seats (exclusing the 100th one) in 99!, which means that 100th seat is free for the 100th person. Also the total sample space is 100!. That means the probabilityof 100th person finding his seat free is 99!/100!=1/100.

What do you think.

A J
Friday, July 25, 2003

1% is wrong.
It seems like the previous two gentelmen did not
take into account the fact that if person K find his place
free he takes it and the rest of the people taking their
places by default including guy #100.

Aharon Tam
Friday, July 25, 2003

The probability of the 100th passenger to get his seet is equal to the probability of the fist (crazy passenger's) seat been taken before the 100th passenger boards. This is because no matter when in the line the first seat is taken, the rest of the passengers will occupy their own seats.

Now , this probability is equal to:

P= P(1st in the 1st seat) + P(1st in the 2nd seat)*P(anyone from 2nd to 99th in the 1 seat) +...+P(1st in the n'th seat)*P(anyone from n'th to 99th in the 1st seat) +.. P(1st in the 99th seat)*P(99th in the 1st seat)

P(1st in the 1st seat) = P(1st in the n'th seat)=1/100;
P(anyone from n'th to 99th in the 1st seat and 2nd to n-1th seats are already taken) = 1/(100-n) + 1/(100-n)*1/(100-n-1) + 1/(100-n)*1/(100-n-1)*1/(100-n-2)...={(100-n-1)! + (100-n-2)! +...1}/(100-n)!


P = 1/100 *[1 + {(100-2)! + (100-3)! +...1}/(100-1)! +  {(100-3)! + (100-4)! +...1}/(100-2)! + .. + {(100-n-1)! + (100-n-2)! +...1}/(100-n)!+ ..

Katya Shilov
Wednesday, July 30, 2003

*  Recent Topics

*  Fog Creek Home