Fog Creek Software
Discussion Board




crazy guy on the airplane

This is a recursion problem.

Let's call P(M) the probability that the last passenger gets his assigned seat, given a 'crazy guy' situation of size 'M', i.e., with M passengers and M seats. We want P(100).

For a crazy guy ('CG') situation of size 'M', let P(M,n) denote the probability that the last passenger gets his assigned seat when the crazy guy ('CG') takes seat 'n'. Since CG's (equally likely) choices partition the outcome space, the final result is:

P(M) = [P(M,2) + P(M,3) + ... + P(M, M-1)]/(M-1).

(Note: P(M,M)=0)

How do we compute each P(M, n)?

If CG chooses seat 'n' then passengers 2..(n-1) get their assigned seats, and passenger 'n' must randomly choose a new one. If he chooses seat 1 ( probability = 1/(M+1-n) ) then each passenger behind him - notably the last one! - gets his assigned seat.

On the other hand, if passenger 'n' rejects seat 1 then the original scenario recurs on a smaller scale: passenger 'n' leads a new virtual 'crazy guy' situation of size (M-n+1). Thus,

P(M, n) = 1/(M-n+1) + [(M-n)/(M-n+1)]* P(M-n+1)

This process is recursed until the last passenger is seated.

(Side note: if the last passenger doesn't get his assigned seat, then he ends up in seat 1; at least he gets to be first one off the plane! :)

Back to the original problem (100 passengers led by the crazy guy):

P(100) = [P(100, 2) + P(100,3) + .. + P(100,99)]/99

where

P(100,2) = 1/99 + (98/99) * P(100,3)
P(100,3) = 1/98 + (97/98) * P(100,4)
...
P(100,98) = 1/3 + (2/3) * P(100,99)
P(100,99) = 1/2.

(someone with a stack deeper than mine can crunch this! :)

Note: Assigning passengers to sequential seats is equivalent to requiring that no passenger may sit until everyone ahead of him is seated.

(hope I didn't screw this up!! :)

Chuck Boyer
Sunday, August 08, 2004

The last guy will never get to sit on any seat except 1 or 100. This fact leads to the probabilty being 1/2. In fact this is true for any number of passengers more than one.

Aryabhatta
Monday, August 09, 2004

Thanks for the comment! :)

"The last guy will never get to sit on any seat except 1 or 100."

True.

"This fact leads to the probabilty being 1/2."

Indeed there are two outcomes, but that doesn't necessarily mean they are equally likely.

"In fact this is true for any number of passengers more than one."

Here are two counterexamples:

For 2 passengers:  crazy guy will certainly take seat 2, so there is zero probability that passenger 2 will get his assigned seat.

For 3 passengers:  passenger 3 gets seat 3 only if crazy guy takes seat 2 (p = 1/2) and passenger 2 takes seat 1 (p = 1/2).  Thus passenger 3 gets his assigned seat with probability 1/4.  The possible seating permutations are (3,2,1), (3,1,2), and (2,1,3); their respective probabilities are: P(3,2,1)=1/2, P(3,1,2)=1/4, and P(2,1,3)=1/4.

Chuck Boyer
Tuesday, August 10, 2004

"The last guy sits in 1 or 100. This leads to probability being 1/2."
I didnt say that this is because there are only 2 outcomes. It just said that this fact leads us to probability being 1/2.
Here is why:

For every combination in which the last guy sits in his own seat we have a combination in which the last guy sits in seat 1 and vice versa.

Consider a combination in which 100 th guy sits in his own seat. Suppose person X is sitting at seat 1 because Y is sitting in X's seat.

Consider the combination where Y is sitting at 100 and X is sitting in X and 100th guy is sitting in 1.

The cases when 1 sits in his own seat or where Y is 1 are easy to map.

We can give a similar mapping in the converse case.

That is why the probability is 1/2 and *not* because there are only 2 outcomes. I was just being lazy.


The crazy chooses a seat a random, so he could choose his own seat. That is how i interpreted it. I think you interpreted it as he chooses a seat apart from his own.

So in the way I interpreted it, probability will be 1/2 for 2 people, 3 people etc.

Aryabhatta
Tuesday, August 10, 2004

Think in a simple way.

When the last person arrive. Every thing is suffled.

100 Seats , 1 Vaccant anf it is random.

P(100th, in 100) is 1/100 or 1 %.

NK
Tuesday, August 10, 2004

"The crazy chooses a seat a random, so he could choose his own seat. That is how i interpreted it. I think you interpreted it as he chooses a seat apart from his own."

Yes, we each considered a different problem even though we read the same 'requirements document'.  I wonder what Humpty* really meant by "... will ignore the seat number on their ticket, ...".  :)

* http://www.sabian.org/Alice/lgchap06.htm

Chuck Boyer
Tuesday, August 10, 2004

I think I'm with chuck's solution here....
Actually I made a little program to calculate the formula and get the exact number. It's taking awfully long because of the recursion, it's been 30 minutes and it's not done yet on my PIII 933 processor.
Will update you with the number when it comes out :)

Christian Kamel
Wednesday, August 11, 2004

If what Aryabhata says is true, then with Chuck's interpretation the probability won't be 1/2. Will it?

Major
Thursday, August 12, 2004

Aryabhata's reasoning yields a simpler way to solve my interpretation of the problem.  Our interpretations are related as follows:

If the crazy guy takes seat F and the last passenger ends up in seat L then, for an M passenger problem, F is either in in {1, 2, ... , M} (Aryabhata's interpretation), or in {2, 3, ... , M} (my interpretation).  In either case L is in {1, M} and

P(L=M) = P(L=M|F=1)P(F=1) + P(L=M|F!=1)P(F!=1)

('!=' means 'is not equal to'; '|' means 'given that')

My interpretation computes P(L=M|F!=1). Aryabhata's interpretation says that the sum is 1/2. Setting P(L=M) to 1/2 yields:

1/2 = (1)(1/M) + P(L=M|F!=1)[(M-1)/M]

or

P(L=M|F!=1) = (1/2)*(M-2)/(M-1)

I hope Christian's calculations get something close to 49/99.  :)

One extra comment, if I may... Aryabhata's solution hinges on: "For every combination in which the last guy sits in his own seat we have a combination in which the last guy sits in seat 1 and vice versa."  This reasoning leads to an answer of 1/2 because, for every such permutation pair, each half of the pair has the same probability - i.e., whenever a passenger finds his assigned seat occupied, he is as likely to choose seat 1 as he is to choose seat 100.  This might have been obvious to some, but I had to think about it for a minute.

Follow-up question: On average, how many passengers get their assigned seat? ;)

Chuck Boyer
Thursday, August 12, 2004

I'm sorry, I left the thing running for 10 hours and it didn't reach a result, I'm sure the code is OK with no infinite loops or anything cuz I got results for up to 30 ppl.
For 5ppl the probability worked out to 0.125 or 1/8
For 10 it's 0.05555
For 15 it's 0.03571
for 20 it's 0.026316
Do these numbers ring any bells ? They don't for me...

I am beginning to think there is gotta be a more elegant solution....

Christian Kamel
Friday, August 13, 2004

And there is the code in c++ in case anyone wants to take a look at it...

float SolveCrazyGuy (int iPassengerNumber)
{
    float fProbSoFar = 0;
    if (iPassengerNumber <= 2);
    else
    {
        for (int i=2; i < iPassengerNumber; i++)
        {
            fProbSoFar += GetProb(iPassengerNumber, i);
        }
        fProbSoFar /= iPassengerNumber-1;
    }
    return fProbSoFar;
}

float GetProb(int iPassengerNumber, int iCrazyGuySeat)
{
    if (iCrazyGuySeat == iPassengerNumber-1)
        return 0.5;
    else
        return (
            1/(iPassengerNumber+1-iCrazyGuySeat)
            +
            (
             (iPassengerNumber-iCrazyGuySeat)/(iPassengerNumber-iCrazyGuySeat+1)
             * SolveCrazyGuy(iPassengerNumber-iCrazyGuySeat+1)
             )
             );
}

Christian Kamel
Friday, August 13, 2004

while chin scratching for a more elegant solution I think I may have found one.
Let's try to find the probability that the last guy DOES NOT sit in his place, that is seat 100 is already taken by anyone by the time he gets on the plane. If we get this P(100) we can easily get the other one as 1 - P
If seat 100 is already taken then it must have been taken by any of the previous 99 passengers. So the combined probability is
P(1, 100) + P(2, 100) + P(3, 100) + ...... + P(99, 100)
where P(1, 100) is the probability of the first guy (the crazy guy) to sit in the chair no. 100, P(2, 100) is the probability of the second guy sittin in the chair 100, P(3, 100) is the probability of the 3rd guy sitting in the chair 100 and so on.

Crazy Guy would sit in the 100th chair only if he chooses it from among the other 99 so
P(1, 100) = 1/99 since the crazy has 99 seats to choose from
Now the second guy would only sit in chair 100 if #1 guy (cz) sat in his chair and then he chose chair no. 100 to sit in, that is
P(2, 100) = 1/99*1/98
The 3rd guy has more cases, first guys sat in 2, 2nd guy sat in 3 and then he chose 100, or first guy sat in 3 and he chose 100 so
P (3, 100) = 1/99 * 1/98 * 1/97 + 1/99 * 1/97
The 4th guy's probabilty is
P (4, 100) = 1/99*1/98*1/97*1/96 + 1/99*1/98*1/96 + 1/99*1/96
In words that is

After writing it all down I'm wondering if this one is really more elegant :)

Does anybody think this has a chance?

Christian Kamel
Friday, August 13, 2004

I've been flooding this thread with messages sorry about that but I realized a minor glitch in my previous calculations, the concept should be correct but the numbers should be:

P(1, 100) = 1/99
P(2, 100) = 1/99*1/99 (not 98 because guys #2 has all seats to choose from except his, so 99 seats)
Accordingly
P (3, 100) = 1/99 * 1/99 * 1/98 + 1/99 * 1/98
and
P (4, 100) = 1/99*1/99*1/98*1/97 + 1/99*1/99*1/97 + 1/99*1/97

So basically I just forgot one chair out of all the cases.
And it may be worth mentioning that numbers from this method coincide nicely with the numbers from Chuck's method, I tested it for small cases of 2 to 5 people.

Christian Kamel
Friday, August 13, 2004

Christian, I admire your perseverence! :) 

If my alternative approach is right, though, I'd have expected the solution sequence you calcuated to converge to 1/2. 

There may be a subtle error on one line of your 'SolveCrazyGuy' function.

Instead of  fProbSoFar /= iPassengerNumber-1;
try  fProbSoFar /= (iPassengerNumber-1);

I'also m thinking the number of iterations is some function of M factorial (M!), in which case this problem could take a *very* long time to compute. :)

Not surprisingly, your proposed approach looks fine to me. ;) 

Chuck Boyer
Saturday, August 14, 2004

Thanks Chuck :)
Well, I'm afraid the numbers do not converge to 0.5, actually the number is already 1/8 for a plane of 5 people. And it keeps getting lower.

I changed the line but the results are the same, so I guess operator precedence took care of this one, I like to make sure always though so I'm keeping this change.

I am still working on implementing my formula in code and see if we can get a result faster, I am expecting the new code will be of complexity O(n squared) instead of the O(n to the power n) we're looking at now.

I've never actually written any useful code of this order of complexity, this should be the first. That is of course if you consider solving the puzzle useful :)

Christian Kamel
Saturday, August 14, 2004

Surprise Surprise
I turned my solution to code and I got 0.947 something probability that the 100th guy sits in his own seat.
Actually the results are the exact opposite of the earlier solution, the probability for the last guy to be seated in his own seat increases with the number of passengers in my solution.

Chuck, your solution yields decreasing probability with increasing passenger number. I guess there is gotta be some mistake there.....
And I've lost all hope that my code for your solution will give us a number, 5 hrs is not enough for it to compute the probability for 40 passengers.
The other solution's (mine that is) code works like charm though, the code is of O(n squared) complexity

Christian Kamel
Saturday, August 14, 2004

I still admire your perseverance, Christian! :)

FWIW, I've only encountered one occasion in which a recursive function was the clean way to solve to a particular problem, and it rarely had to go more than 3 iterations deep.  Even the canonical example of computing N! is usually done more easily by iteratively multiplying up from 1 than by recursion.

In doing some manual calculations for low M, I did notice that my approach produced decreasing probabilities. So something's certainly wrong somewhere with one of the solutions.  I think the crux is to be sure the sample space gets correctly defined and partitioned.  At least I'll have something to think about during my morning runs. ;)

Chuck Boyer
Sunday, August 15, 2004

Christian, I think you might have overlooked something in implementing your approach. :(

If your program follows the pattern you laid out above, I don't think your P(n,100) calculations account for all of the seating permutations when n > 3. 

Specifically, It looks like your expression for P(4,100) skipped one of the permutations that place guy 3 in seat 4. 

Here's the pattern, revisited:

(Note: extended n-tuples, e.g. (100,1, ... ,2),  represent seating permutations.)

P(1,100) = P(100, ... ,1) = 1/99

P(2,100) = P(100,1, ... ,2) = 1/99 * 1/99

P(3,100) = P(100,1,2, ... ,3) + P(100,2,1, ... ,3)
= (1/99 * 1/99 * 1/98) + (1/99 * 1/98)

P(4,100) = P(100,2,3,1, ... ,4) + P(100,1,3,2, ... ,4)
+ P(100,1,2,3, ..., 4) + P(100,2,1,3, ... ,4)
= (1/99 * 1/97) + (1/99 * 1/99 * 1/97)
  + (1/99 * 1/99 * 1/98 * 1/97) + (1/99 * 1/98 * 1/97)

Looking ahead,  P(5,100) will have 7 permutations:
(100,2,3,4,1, ... ,5)
(100,1,3,4,2, ... ,5)
(100,1,2,4,3, ... ,5)
(100,2,1,4,3, ... ,5)
(100,1,2,3,4, ... ,5)
(100,2,1,3,4, ... ,5)
(100,2,3,1,4, ... ,5)

It looks to me like each P(n+1, 100) will have to account for 'n' more permutations than P(n,100).  It wasn't clear to me that your approach was doing that.

Chuck Boyer
Monday, August 16, 2004

I forgot one P(5,100) permutation; the (reordered) permutations for seats 2..5 are:

2 3 4 1
2 3 1 4
2 1 3 4
2 1 4 3
1 3 4 2
1 3 2 4
1 2 4 3
1 2 3 4

This renders my conjecture about the permutation count incorrect.

Guess my brain was still hypoxic from running. ;)

Chuck Boyer
Monday, August 16, 2004

you're pretty much perseverant yourself :)

Well I see your point , but I guess my code implementation already accounts for that, it seems like I just forgot to put it in when explaining the formula.

So I'm wondering does that mean the numbers I get are correct?

I tested on 5 ppl plane and I think my solution got 1/3 probability, while my code for yours gave 1/6.
Trying the permutations by hand it seemed 1/3 is about right.

Also I checked other forums, it seems many other people understood the "requirements document" as such that the crazy guy may end up on his own seat after all. I think this would be a minor tweak in my formula to start with P(1, 100) to be 1/100 instead of 1/99.....

Christian Kamel
Monday, August 16, 2004

Some think I'm obsessive. ;) 

We *are* bludgeoning a dead mouse with a sledgehammer, aren't we! ;) But it bugs me to miss a logic error and I frankly don't see a flaw in either approach. :/  I should reinstall my compiler and do some exploratory crunching of my own to look for clues and sharpen the edge a little. I shouldn't have confused the operator precedence of '/=' with that of '/' ! ;)

Ya know, if the 'spec' had said the crazy guy ignored 'the number' on his ticket rather than 'the seat number' on his ticket, I might have leaned toward the other version of the problem. But it's also possible my understanding of 'ignore' might be warped.  (I love that Humpty Dumpty dialog in TTLG! ;)

Well, I've used up the rest of my spare time for the year on the puzzles here so I should probably quit scribbling and do something useful.  ;) 

Nice puzzling with you, Christian! :)

Chuck Boyer
Monday, August 16, 2004

Still obsessing, but almost done... ;)

First, I erred in my original comment when writing the illustration for M = 100; it should have read thus:

P(100) = [P(100, 2) + P(100,3) + .. + P(100,99)]/99

where

P(100,2) = 1/99 + (98/99) * P(99)
P(100,3) = 1/98 + (97/98) * P(98)
...
P(100,98) = 1/3 + (2/3) * P(3)
P(100,99) = 1/2. (= P(2) )

~~~~~~~~

I enumerated the permutations for the 5-seat problem and used your approach to manually calculate their probabilities. This yielded P = 3/8 for the permutations with guy 5 in seat 5, while the remaining permutations added up to  P = 5/8, as they should have.

If you use the formula I got when melding Aryabhatta's result with mine, you get:

P(L=5 | F!=1) = 1/2 * (5-2)/(5-1) = 3/8

which matches the result obtained by enumeration; not a proof of correctness, but at least a small comfort. ;)

I may repeat for M=4, and do the recursion manually to see how it goes. If I got things wrong, I want to know why. (what else does a geek have to spend his personal time on? ;)

Chuck Boyer
Monday, August 16, 2004

Alrighty then.... ;)

Well, I manually solved for M=3, M=4 and M=5 using all three approaches - enumeration, recursion and the formula.  In each case, all 3 approaches gave the same answer:

P(3) = 1/4;  P(4) = 1/3;  P(5) = 3/8;

I have a a little confidence that my approach wasn't too far afield and that the formula

  P(M) = 1/2 *(M-2)/(M-1)

gives the correct result for this interpretation of the problem.

FWIW, I found it easier to compute successive P(M) results "bottom up", using each P(k) to compute P(K+1) - like computing a factorial by iteration rather than literal recursion.

:)

Chuck Boyer
Monday, August 16, 2004

Proof by Induction:

2 seats on an airplane:
Crazy guy gets on first, chooses a random seat.
1/2 chance he sat in his own seat
1/2 chance he sat in the last guy's seat
Chances the last guy sits in his own seat: 50%

3 seats on an airplane:
Crazy guy gets on first, chooses a random seat.
1/3 chance he sat in his own seat
1/3 chance he sat in the last guy's seat
1/3 chance he sat in passenger 2's seat.
In this last case, it reduces to the 2-passenger scenario, which we already know is 50%
Chances the last guy sits in his own seat: 50%

....

100 seats on an airplane:
Crazy guy gets on first, chooses a random seat.
1/100 chance he sat in his own seat
1/100 chance he sat in the last guy's seat
98/100 chance he sat in another passenger's seat.
In this last case, it reduces to the n-1 passenger scenario, which we have already determined has a chance of 50%

Chances the last guy sits in his own seat: 50%

-----

Another simple description:
Any passenger who chooses a seat at random has an equal chance of choosing the seat of passenger 1 or 100. If they choose 1, then all remaining passengers can sit in their own seat. If they choose 100, then the last passenger will not be able to sit in their assigned seat. Any OTHER choice (one of the other open seats) simply defers the decision to a later point in time, where THAT deposed passenger will have to make the same random choice.

Chance: 50%

Brad Corbin
Wednesday, August 18, 2004

Concerning the "can the crazy guy pick his own seat" debate:

Technically, if he's ignoring the seat number on his ticket, he has to be able to pick his own seat. In other words, in order for him to NOT be able to pick his own seat, he'd have to know what his own seat is, and therefore not ignore it. We know that he ignores it however, and therefore should be able to pick it.

That's my take.

Zach Wily
Tuesday, August 24, 2004

Good point, Zach!

I saw it more as a matter of interpretation than debate. :)  To me it hinges on whether crazy guy is ignoring the number or the seat. 

FWIW, I colloquially use "seat number" and "seat" synonymously when referring to a specific seat... e.g., "seat 3" and "seat number 3" mean the same thing to me, but  I recognize that others may (and obviously do) use the language differently.

If he's ignoring the seat, then to him that seat doesn't exist -- which was my (apparently weird ;) interpretation.  In that case, the number tells him which seat to 'ignore'. ;) 

OTOH, if he's ignoring the number then what you said makes sense to me.

I'm happy with either interpretation. When in Rome, ...

;)

Chuck Boyer
Tuesday, August 24, 2004

I threw together some C code to actually run the scenario millions of times and see how many times the last guy ends up in his seat. For 100 seats run 100M times, I keep getting the last guy in his seat 49.94% of the time.

Here's the code:

#include <stdio.h>

int run(int numseats)
{
    int *seats = (int *)malloc(sizeof(int) * numseats);
    memset(seats, 0, sizeof(int) * numseats);
   
    // special case crazy guy
    int seat = random() % numseats + 1;
    seats[seat - 1] = 1;
   
    int i;
    // continue with second dude
    for (i = 2; i <= numseats; i++) {
        if (seats[i - 1]) {
            // his seat is taken, randomly choose another
            int newseat;
            do {
                newseat = random() % numseats + 1;
            } while (seats[newseat - 1]);
            seats[newseat - 1] = i;
        } else {
            // sits in his own seat
            seats[i - 1] = i;
        }
    }
    // is the last guy in his own seat?
    int ret = (seats[numseats - 1] == numseats);
    free(seats);
   
    return ret;
}

int main(int argc, char *argv[])
{
    if (argc < 3) {
        printf("usage: %s number_of_seats iterations\n", argv[0]);
        exit(0);
    }
   
    int numseats = atoi(argv[1]);
    int iterations = atoi(argv[2]);
   
    srandomdev();
   
    int succeed = 0;
    int i;
    for (i = 0; i < iterations; i++) {
        if (run(numseats)) {
            succeed++;
        }
    }
   
    printf("last guy sat in last seat %.2f%% of the time\n", (float)succeed / iterations * 100);
   
    return 0;
}

Zach Wily
Tuesday, August 24, 2004

Thanx for the code zach.
It's now established that for your interpretation of the problem (the one most ppl understood and what probably was meant by the author) the probability is a constant at 0.5 regardless of the no. of the ppl on the plane.

I was anxious to look at results for the other interpretation though, the one Chuck and I understood from the puzzle when we first read it.
So I just replaced this line in the code of urs and ran it:
// special case crazy guy
//Let's comment this one out and add our interpretation
//int seat = rand() % numseats + 1;
int seat = (rand() % (numseats-1)) + 2;

This causes the crazy guy always to ignore his seat.
The results comply with earlier calculations but they doesn't seem to follow a specific trend, they grow fast untill they hit 0.5 at which limit they grow but very slowly.
For example at 100 passengers the probability was around 49.5, with 1000 passengers it was around 50.5, and with 10,000 passengers it's around 57%

I guess this is fair enough, and I think Chuck and I "misinterpreted" the puzzle because obviously the other interpretation has the more elegant solution so it wins :)
I am happily letting go of this one now :)

Christian Kamel
Tuesday, August 24, 2004

Now that we have settled on a common interpretation:

Here is another way of looking at it which might be more convincing.

Take any arrangement of the people which could occur.
It is a permutation of (1,2,....n) with the following properties.


1) There is atmost one cycle of length more than 1.
2) If there is a cycle of length more than 1, then person 1 is in it.

Any permutation is a set of disjoint cycles. Start at a particular person and follow the chain till you get back.
Eg (3 4 2 1) is a permutation which has the cycle 1->4->2->3->1 which is of length 4 (read the arrow as 'goes to')
(3 2 1 5 4 6) is composed of cycles
1->3->1 of length 2
2->2 of length 1
4->5->4 of length 2
6->6 of length 1


Any permutation of (1,2...n) satisfying properties 1 and 2 is a valid seating arrangement.

We are looking for the probabilty that a permutation has the cycle 100->100.

Aryabhatta
Wednesday, August 25, 2004

It is simple !! when 100th person boards in ...he will either get the 100th seat empty or occupied ...so probability is 1/2 :D

Akhil Gupta
Thursday, September 02, 2004

For the 1000th time this is mentioned here, having 2 possible solutions does not "automagically" make each solution's probability = 1/2 !!
And just because this one's probability is really actually half doesn't mean your line of reasoning is right, there are plenty of other problems with 2 outcomes but with each outcome's probability different than 1/2 !

Christian Kamel
Friday, September 03, 2004

I am not sure I get the .5 probablity reasoning ,,
The crazy guy can randomly sit in 100 different seats. Which means there is at most one and only one chance that he might sit in his own seat out of a 100 chances. So therefore the chance that the last guy sits in his own seat is just 1/100 i,e 1 %

SM
Monday, September 06, 2004

I think stating that the probability is 1/2 is not totally correct.
All conditions are not equal.
For example the crazy chain of event occur only if the first guy does not take is own seat. The first guy makes an independent decision and other people don't.

So there is a 1/100th chance that the last guy gets his own seat (if the first guy sits at his own seat).

In the other 99/100 cases there is a 50% chance, so the total probability is 99/200 + 1/100 = 50.5

Krish
Thursday, September 16, 2004

Please ignroe my last mesange. I realsie that it was incorrect reasoning.
The answer of 0. seems to fit the pattern for 2,3,4 passengers but I am still not convinced that it is 0.5

Someone suggested mathematical induction. That seems the best way to prove it.

Thanks
Krish

Krish
Saturday, September 18, 2004

Poor spelling in my last mail:
Please ignore my last 2 messages. I realise that the reasoning was incorrect.

The answer of 0.5 seems to fit the pattern for 2,3,4 passengers but I am still not convinced with any of the proofs offered for this result.

Someone suggested mathematical induction. That seems the best way to prove it.

Thanks
Krish

Krish
Saturday, September 18, 2004

-----"For the 1000th time this is mentioned here, having 2 possible solutions does not "automagically" make each solution's probability = 1/2 !!"----

But the answer is 1:2

Because at any one stage there are only two seats that matter. The 100th seat and the seat that should have been taken by an earlier passenger and hasn't. The odds of either being taken are equal and remain that way throughout. The original crazy guy has a 1:100 chance of taking his own seat and a 1:100 chance of taking seat 100. If he takes his own seat everything is ove, just as it is over if the takes seat 100. If he takes neither then the next guy that comes and finds his seat taken has a 1:n chance ot taking the seat of a person sitting in the wrong place and a 1:n chance of taking seat 100.

Stephen Jones
Sunday, September 19, 2004

Formal proof by induction:

Theorem: For all number of passengers, n>=2, the chance of the final passenger getting his or her assigned seat is 50%

Method: Prove for n=2, and prove that n implies n+1.

n=2:
With only two seats, the first passenger can only choose his own seat and the seat of the final passenger. 50% chance to choose his own seat means a 50% chance the final passenger will get his own seat.

n->n+1:
Let us assume that for n passengers, the chance of the final passenger choosing his own seat is 50%.
For n+1:
The first passenger has n+1 seats to choose from: his own, the final passenger's, and the n-1 other seats. Probability of the first passenger randomly choosing each:
His own: 1/(n+1)
Final Passenger's: 1/(n+1)
Other passenger's: (n-1)/(n+1)

But we know that if he sits in one of the other seats, then we are reduced to the problem with n passengers: We have n remaining seats, n remaining passengers, and one passenger is displaced by the first passenger and therefore must choose a seat at random.

So the chance of the final passenger sitting in his own seat is equal to:
1/(n+1) + 50% of (n-1)/(n+1) = (2+(n-1))/2(n+1) = (n+1)/2(n+1) = 1/2

So n implies n+1, QED.

Brad Corbin
Monday, September 20, 2004

Hi Bard Corbin,
Thanks for the proof, that sounds pretty solid. Mathematical induction is simple yet really powerful.

krish
Monday, September 20, 2004

We could find this out based on the probablities that
seat-100 will be empty after each guy takes a seat.

Prob that crazy guy does not take seat-100 = 99/100
Prob that guy#2 does not take seat-100 = 98/99
...
...
Prob that guy#98 does not take seat-100 = 2/3
Prob that guy#99 does not take seat-100 = 1/2



Prob that guy#100 gets his own seat = product of all the
above probabilities = 1/100

Dhanju
Saturday, October 02, 2004

Regarding the FORMAL PROOF BY INDUCTION:

There is a flaw in your logic.  You said:

>But we know that if he sits in one of the other seats, then we are reduced to the problem with n passengers: We have n remaining seats, n remaining passengers, and one passenger is displaced by the first passenger and therefore must choose a seat at random.

The problem is you have only shown that it is 0.5 if the FIRST passenger is displaced.  In this case the first few passengers can take thieir correct seats and some later passenger will be displaced.    So the formulation is really more complicated than what you show.  (I believe that it comes out correctly in the end, but I have not found a nice, clean, formal way to express the proof given this extra wrinkle.  Can anyone else?)

rahs
Thursday, October 07, 2004

I had my class conduct trials of the scenario with 20 students and seats in a classroom.  In 10 trials, the last student to enter the room got his correct seat 5 times.  So I am convinced it is fairly close to 50% probability, though I can't prove it.

jones
Friday, October 08, 2004

50% doesn't seem logical to me.  And at the same time it does.

There are 100 possible seatings (or instances of a person putting their butt in a chair.) 

There is only really one seat we are worried about - the 100th passenger's any other seat can be occupied by any other butt, no issues.

So, what we need to calculate is the odds of each passenger sitting in the 100th passenger's seat (#100, let's guess)

So the odds of the crazy guy sitting in seat#100 is 1/100.  Assuming he doesn't sit in seat #100 (otherwise, the odds are 0) the odds of the second passenger sitting in seat #100 is 1/99 (choices being completely random).

...having gotten this far, I have changed my mind.

What needs to be considered is the probability of EACH passenger having their own seat available, down to the last passenger (ie: two people have randomly chosen each OTHER's seats).

So the odds of the second person having their seat available is 1/100 (the crazy guy might have chosen his own seat, after all).  The odds of the 3rd person having his own seat available is 1/100 (it relies on the first condition being true) * 1/99 and so on.

I think one of the folks earlier who remembers more of math than I do has arrived at a similar conclusion with incorrect arithmetic.

The final answer should be:

1.0715E-158

It's been a long time since high school - someone let me know if there is a flaw in my logic?

80083r
Saturday, October 09, 2004

wait, now... those are the odds of EVERYONE being in the correct seat.

d'oh!

80083r
Saturday, October 09, 2004

There are two cases:
1) CG takes own seat
    then passenger #100 gets her assigned seat,
    probability 1/100
2) CG takes other seat
    then seating is random, probability that #100
    gets her seat is 1/99

Answer: 1/100 + 1/99

rai
Wednesday, October 20, 2004

Why don't people read first !!!

Reinvent the square wheel.
Wednesday, October 20, 2004

Crazy guy has 1/100 chance of selecting his assigned seat.  All other passengers fall in line. Nth guy's chances hinge on crazy guy's chances making Nth guys chances of getting his own seat 1/100. 

Also, think this way, Crazy guy does not pick his own seat, assume every subsequent passenger to board the plane picks the NEXT persons seat (#1 takes #2's seat, #2 takes #3's seat etc), so nobody is sitting in their own seat. Or even just assume complete chaos.  After all is settled, there's 1 seat open out of 100 -  Nth guy's chances are 1/100 either way you look at it.

Randall Lynch
Wednesday, October 27, 2004

cow moo .i had a baby in an air plane bathroom well flying to gasweeraterania i am 11 and live in a splean. i am a boy

cow moo
Monday, November 01, 2004

cow moo. i had a nother baby on a bean bag its name is moomoo.it is a he she hehehehehe lame guy is my husband

cow moo
Monday, November 01, 2004

cow moo this husband of mine is a stuck up jerk wad he made out with moomoo my baby 23 yearold this sucks

cow moo
Monday, November 01, 2004

dolt head . pollid es anson i have a chacha  gupy who i like yo hump alot he is so sexy

tttt
Thursday, November 04, 2004

*  Recent Topics

*  Fog Creek Home