Fog Creek Software
Discussion Board




crazy guy on airplane

I guess the everyone sitting in the right place solely depends on the crazy guy's decision.

Since he selects his seat at random, the probability that the crazy guy will select his assigned seat is 1/100.

So, the probability that 100th person will be in correct seat is also 1/100.

Apurva Sinha
Friday, April 09, 2004

What the person after Crazy Guy, seeing that his/her seat is already taken, by chance picks the seat of Crazy Guy?

Vigor
Friday, April 09, 2004

1st guy chooses the 100th seat with a prob. of 1/100. So the prob. that the last guy gets his seat is 99/100. Similarly, after the second guy has made his choice, there is a 98/99 chance that the last guy gets his choice. So, this way we have:
99/100 * 98/99 * ... *2/3 * 1/2 = 1/100

Is this right? If not, pls post the right answer

RJ
Tuesday, April 13, 2004

I beleive that you can compute it as follows:
There are two possibilities for the last guy to get his seat:

a)  either the first guy picks his own seat: 1/100 and everybody else sits where they should.

b)  no-one sits in the last guys seat: 99/100 * 98/99 ... * 2/3 * 1/2 = telescopes to 1/100. 

Summing these two possibilities we get: 1/50

gbizzle
Wednesday, April 14, 2004

All suggestions so far ignore the case where crazy guy takes seat n, and passenger n (by chance) takes seat 1. All passengers after n would find their usual seats empty, and would not pick a random seat.

I think this is a recursive problem. Assume passenger 1 (the crazy guy) takes place n, where n > 1 and n < 100. Passengers 2..(n-1) will find their normal seats.
Passenger n is now in the same situation as passenger 1 was: He picks a seat by chance, although not 1 of 100, but 1 of (101 - n). If he takes seat 1, things go normal after him, if he doesn't, things go crazy. Assume he picks seat m, with m > n and m < 100. Passengers (n+1)..(m-1) will pick their normal seats.
Passenger m is in the same situation as passenger 1 and n were. If he picks seat 1, things will go normal for the passengers (m+1)..100 . . . and so on.

So it's useful to generalize the problem to one of N seats. I believe it is possible to prove by induction that the chance that the last guy gets his seat is exactly 1/2 for all N >= 2.

You can quickly verify this for N = 2, 3, 4 (because you can still draw the complete tree). I have written a small simulation for the problem with N = 100 (as in the original question), and after a few thousand runs it comes up with something very close to 0.5.

I have a half finished proof here that the probability is really 1/2. If nobody else publishes a complete solution, I'll post mine. But I wont have time for a couple of days.

Vigor
Thursday, April 15, 2004

Ok, I got the solution.

I will use pn to mean person# n and sn to mean seat# n.

p1 has 1/100 chance of taking each of the 1-100 seats. Let us look at what chance p100 has based on each of p1's 100 choices.

Case 1: p1 takes s100. Chance of p100 = 0;

Cae 2: p1 takes s99. Then p2 to p98 will take their resp. seats. p99 can take either s1 or s100. if he takes s1, p100 gets s100. so chance of p100 = 1/2;

Case 3: p1 takes s98. p1 tp p97 are all set. Now p98 has 3 choices. He can take s100 in which case p100 has chance = 0; if s98 chooses s99 with a probability of 1/3, p99 can choose s1 with a probability of 1/2, so that gives p100 a chance of 1/2 * 1/3 = 1/6. If p98 chooses s1 with a probability of 1/3, p100 has a chance of 1 to get s100. So the total chance of this is case is 0+1/3+1/6 = 1/2.

For all such cases, the probability will always work out to half.

In the last case, when p1 chooses s1, p100 has prob. 1 to get his seat.

Each of these cases are independent.

So total probabilty = 0 + 1/100 * 1/2 + 1/100 * 1/2 ... + 1/100 * 1

= 1/100 * ( 1 + 1/2 + 1/2 ... 98 times)

= 1/100 * ( 1 + 98/2)

= 1/100 * (49 + 1)

= 1/2

RJ
Monday, April 19, 2004

The answers one in two. It has been explained half'a'dozen times but the threads keep disappearing. The point is that there is always a fifty percent chance that the one person without the correct seat will pick the crazy guys seat and set everything back to normal.

Another way to do it is to imagine only two, three or four seats.

Two seats ' 50% chance first time.

Three seats a) he takes his seat  100% success
                  b) he takes the last seat 0% success
                  c) he takes the middlle seat 50% success depending on what the next guy does

Four seats a) he takes his seat 100% success
                b) he takes the last seat 0% success
                c) he takes one of the middle seats and you're back to the situation with three seats 50%

And now it becomes clear that with five seats he either takes the first or last seat, or takes  a middle seat in which case you get to the case with four seats and so on.

Stephen Jones
Monday, April 19, 2004

Yes, pity that the threads continue to disappear.
What are the seats can possibly be empty when the last guy enters? It could be his own. It could be the crazy's one. Can it be any other seat? No, since if it is, for example, seat of the guy number 40, it remained non-occupied all this time -- and then nothing could prevent the guy number 40 from taking it.
So, the last guy with prob. 1 gets either his own seat, or the crazy's one. But after the crazy enters and sits down, this two seats are absolutely equial to each other in the experiment for the rest of the time. Thus, the last guy gets his seat with prob. 1/2

DK
Saturday, May 01, 2004

The simplest way to look at it:

The only choices that MATTER are if someone n<=99 randomly selects seat #1 or seat #100.

This could be passenger #1 or a later passenger displaced by a previous.

If seat#1 is randomly chosen at some point by some passenger, passenger 100 can sit in their own seat. If someone randomly chooses seat #100, then he can't.

All other seat choices simply defer the final decision to another later passenger.

So the true chances of one PARTICULAR passenger choosing seat 1 or seat 100 will vary depending on their passenger #, but the chances of choosing seat 1 or 100 are always equal.

So, the ultimate chance that passenger 100 sits in his own seat is 50%.

Brad Corbin
Wednesday, June 09, 2004

*  Recent Topics

*  Fog Creek Home