Fog Creek Software
Discussion Board




crazy guy on the airplane

If the last person can't seat in his seat, the only seat he can sit on is the first seat. So the possibility he can't seat in his seat is equal to the possiblity that nobady chooses the first seat. the possibility is 99/100*98/99*97/98...1/2=1/100. So the possibility he will seat in his seat is 1-1/100=99/100

yong
Wednesday, December 10, 2003

Actually, the answer is that the last guy has a 50% chance of sitting in his assigned seat.

peter
Friday, December 12, 2003

The answer is 1/100.  Assumptions are that all seats are equally likely of being chosen, with a single trial being one person choosing or not to sit in the first seat, and success being the that person sitting in that seat, and a failure being that person not sitting in that seat.  Then the probability that the seat will be available after 99 other people have chosen seats (after 99 independent trials, each with a failure result, calculated using permutations) is 99/100 * 98/99 ... * 2/3 * 1/2 = 1/100.
This is the sum of N from 2 to 100 of (n-1)/n; also calculated as (n-1)!/n! with n = 100.  Also one can consider that if all seats are equally likely of being chosen, then the probability of the one seat being unchosen, out of 100 possible seats, is 1 out of 100.  See "A First Course in Probability" by Sheldon Ross, 6th Ed. Ch 1, Sec 1.3 Permutations.

Mark Benson
Tuesday, December 16, 2003

Isn't the solution a 1/2?  For instance the last explanation says the number permutations in which the last passenger will be seated in his assigned seat is (n-1)! ,(where n is the number of seats) and the total number of ways that passengers can be seated is n!.  This does not take into account the fact that a passenger will sit in his assigned seat if it available.  For instance suppose n = 3.

The permutations that satisfy the constraint that a passenger will go to his seat if it available is:

123 ,213 ,312 ,321

The permutations in which the last passenger will be seated in his assigned seat is

123, 213.

which result in 1/2 chance the last passenger will be seated in his assigned seat.

In  general the number of permutations on n seats which satisfy the constraint that a passenger will go to his seat if it is available is 2^(n-1) and the number of permutations in which a last passenger will be seated in his assigned seat is 2^(n-2).  Hence the answer is 1/2.  Peter was right (I think).  This can be proved using induction with n=2 as a base case.

Jeff
Tuesday, December 16, 2003

There are two ways that I determined that the answer to this problem is 50%: first, I modeled the problem on the computer; second, consider a simpler version of this problem where there are only two seats--which is easy to solve, then apply the same process to higher numbers of seats. You should be able to see that the answer for n seats is recursively related to the answer to the ( n-1 ) seat problem. Done.

peter
Wednesday, December 17, 2003

Well here is a formal proof:

Let T_n represent the total number of valid permutations and let L_n represent the total number of permutations where the last passenger will get to sit in his assigned seat on n seats and passengers.  We want to show that

T_n = 2^(n-1) and L_n = 2^(n-2)

Base Case: n=2

The valid permutations is 1,2 and 2,1 and the permutation where the last passenger gets to sit in his assigned seat is 1,2.  Hence

T _2= 2^(2-1)=2 and L_2 = 2^(2-2) = 1

Hypothesis:  For n = k the total number of valid permutations and the total number of permutations in which the last passenger can be seated in his assigned seat is

T_k = 2^(k-1) and L_k = 2^(k-2)

respectively.

Suppose that we add another seat to the plane.  We now have n = k+1.  Notice the (k+1)th passenger can only be seated where the first passenger is supposed to sit or where he is supposed to sit.  (ie the (k+1)th passenger can only sit in the last seat of the plane or first seat of the plane).  To see this suppose that the (k+1)th passenger sits in the i-th seat where i != 1 and i != k+1.  This means that i-th passenger decided not to sit in his assigned seat.  This is a contradiction because the the problem states that:

All passengers other than the first will sit in his assigned seat if it is not taken.

This means that we get T_k permutations where the (k+1)th passenger sits in the last seat and T_k permutations where the (k+1)th passenger sits in the first seat.  So

T_(k+1) = T_k + T_k = 2^k = 2^(n-1)
L_(k+1) = T_k = 2^(k-1)  = 2^(n-2)

Jeff
Wednesday, December 17, 2003

The answer is 1/2.

here is one way to look at it.

Let the people be number 1,2 ... , n.
Let the person sitting in seat i be p_i.

Now p1,p2,...pn is a permutation of 1,2,...n with the following properties:

1 ) The permutation has atmost one cycle of length > 1.
2) The cycle of length > 1 contains the number 1.

Also, any permutation satisfying 1) and 2) corresponds to exactly one possible seating arrangement. So there is a 1-1 correspondence between the possible seating arrangements and permutations satisfying 1) and 2).

Looking at permutations, we can see that pbt that 1 and n are in the same cycle = 1/2.

Aryabhatta
Monday, December 29, 2003

Simpler solution:

Remarks:

1. The 100th guy can only be at seat #100 or #1. Seat #67 can't still be available, because otherwise the 67th guy would have sat on it.

2. The 100th guy doesn't decide anything. He takes whatever is available. So, don't mind him.

So, only two possibilities, decided by guys 1 through 99.

Since from everybody's point of view, seat #1 is just like seat #100 (they just look at their own seat as special and 1st guy doesn't look at any seat as special), at the end, #1 being available must be just as likelly as #100 being available.

(Note: you can formalize this reasoning as follows: Let pi be the probability that i is on seat #1 and pi' the probability that i is on seat #100. Define them recursivelly for i to 99. Their definitions will coincide. Use them to calculate p100 and p100').

luis

LUís Pedro Coelho
Monday, January 12, 2004

Reading everybody's post, I think 1/2 is the correct answer.

The solution hinges on the fact that the 100th guy can only be at seat #100 or #1.
Once we have established this, it is easy to see that the answer is indeed 1/2.
For more formal/logical proof, refer to solutions above.
(Specifically, the proof given by Jeff is excellent).

IMHO, there is no convincing proof in above posts that 100th guy will indeed sit on seat #100 or #1.
(Actually Jeff's post above proves this if you read carefully).

Whatever, I am gonna prove that
"The 100th guy can only be at seat #100 or #1"

Let's start analysing different cases.

Case 1: The 1st guy sits in seat #1.
        In this case, everybody sits on his seat. Problem solved.

Case 2: The 1st guy sits in seat #i
        Now, everybody till the i'th guy sits on his seat.
        i'th guy has the option of sitting in any seat with
        number > i and the first one.

        Now there are three cases:
        Case 2.1: if the i'th guy sits on 1st seat,
                  everybody else after him (including the 100th guy)
                  gets to sit on his assigned seat.

        Case 2.2: if the i'th guy sits on seat #100, everybody
                  else after him except the 100th guy gets to
                  sit on his assigned seat. For the 100th guy the
                  only seat left is the first one. So he gets seat #1.

        Case 2.3: if the i'th guy sits on seat #j, everybody else
                  after him till the j'th guy gets to sit on his
                  assigned seat. The j'th guy has the option of
                  sitting in any seat with number > j and the
                  first one.

                  Now same arguments applies for the j'th guy as was
                  for the i'th guy (i.e. Cases 2.1, 2.2, 2.3 repeat
                  for the j'th guy).
                  This continues till we are done.
     
So, we see that in all cases, 100th guy gets to sit on either seat #100 or #1.

(He he...now I am satisfied.)

VikasRana
Wednesday, January 14, 2004

Based on how I interpret the question, the answer is definitely not 1/2.  The first guy is randomly choosing his seat - so there's a 1/100 chance he chooses his assigned seat and so everyone boards property and passenger 100 gets their seat with a 100% probablity (1/100 * 1).  There's also a 1/100 chance the first guy chooses the 100th passenger's assigned seat, so there's no chance of getting their assigned seat (1/100 * 0).  The other 98 cases are not equally weighed.  For instance, if the first guy selects seat 99, the first 98 passengers all board into their assigned seats and the probability that the last passenger gets their assigned seat is 1/2 (passenger 99 either sits in seat 100 or seat 1) (1/100 * 1/2).  This pattern repeats to give us: (1/100 * 1) + (1/100 * 1/2) + (1/100 * 1/3) ...

I've long forgotten my match skills in this area...but the numbers work out to around 1/20 by my calculation.  The only reason I don't like this answer is that it doesn't seem to boil down to a nice round number like 1/2 or 1/100, but based on the way the question is phrased, this is how I see it...

tom
Friday, January 16, 2004

it's one in two. When the last passenger boards the plane the available seats can only be one of two. Either seat 1 or seat 100. Whatever happens with the other 98 seats is irrelevant; the point is that at any stage there is an equal chance of a person choosing between one and a hundred (of course in real life which end they enter the plane from will skew it) Whenever this happens then all other passengers go to the correct seats.

Stephen Jones
Monday, January 19, 2004

Tom extrapolated a bit too quickly. Let see again.

Let p = Probability that 100th guy gets to seat on his assigned seat.

Case 1: 1st guy --> seat #1
    Everybody gets to seat on his assigned seat.
    p = 1

Case 100: 1st guy --> seat #100
    Everybody except 100th guy gets to seat on his assigned seat.
    100th guy gets seat #1
    p = 0

Case 99: 1st guy --> seat #99
    Two possibilities

    #100    #1
    -------------
    99      100
    100    99

    p = 1/2

Case 98: 1st guy --> seat #98

      #99    #100  #1
    -------------------
      98      99    100
      98      100  99
      99      98    100
      99      100  98

      p = 2/4

Case 97: 1st guy --> seat #97

    #98    #99    #100    #1
    ---------------------------
    97    98      99    100
    97    98      100    99
    97    99      98    100
    97    99      100    98
    98    97      99    100
    98    97      100    99
    98    99      97    100
    98    99      100    97

    p = 4/8

I won't try to complicate things by explaining this but you can see that there is a nice recursion.

Since probability of 1st guy choosing a particular seat is 1/100, the overall probability is
p = (1/100) * (1 + 0 + 1/2 + 1/2 + 1/2 ....)  -> total 100 terms
  = (1/100) * (50)
  = 1/2


Here's how my one of my friend put it logically.

Consider seats 2-99 a big black box.
When 1st guy don't go into the black box (i.e. doesn't sits on seats 2-99)
p = 1/2.

When 1st guy goes into the black box (i.e. gets to sit on any of seats 2-99), somebody from guy 2-99 won't get a seat and has to come out of the black box. Note that as soon as anybody gets out of the black box, order will be restored within the black box and there is no chance that anybody else would come out also. Now, for the guy coming out of the black box, there are only two seats - seat #1 and #100. He can choose either seat #1 with a probability of 1/2.

So the overall probability is 1/2.

VikasRana
Monday, January 19, 2004

Thanks VikasRama - I now see the flaw in my logic (I suspected there was one, if the numbers aren't nice...it's probably not a cool question ;-).  The comment about "order will be restored within the black box" turned the light on for me.  I was looking past the fact that some passagers will still have their assigned seat open even after previous passengers have had to choose a new seat. Thanks :-)

tom
Saturday, January 24, 2004

Here's an explanation that doesn't involve complicated mathematics.

We have two possible conclusions to our scenario:
1) The chain is broken when someone sits in the crazy guy's seat, resulting in passenger 100 getting his seat.
[Yes, that DOES stop the chain - if someone sits in the crazy guy's seat then passenger 100 WILL get his seat!]
2) The scenario is over if someone sits in the seat of passenger 100 because that means he loses his seat.

At any given point in time, we have an equal chance of either conclusion hapenning (in a random seat selection).

So the odds are 1 in 2 as most are saying.

Marc Peabody
Thursday, January 29, 2004

The answer is 1/4. Here is my logic.
Let N be the number of seat and passengers. Lets do some iterations over N. Calculate prob(N) that passenger N gets his own seat.

For N=2, chance that passenger 2 gets his own seat is 0, given that 1 does not take seat 1. prob(2) = 0.

For N=3
It is a given that person 1 does not take his seat. Person 3 gets his seat is when person 1 chooses seat 2 (with chance 1/2), after that person 2 selects seat 1 (again with chance 1/2 since 1 and 3 are left). So probably in total is so prob(3) = 1/2 * 1/2 = 1/4.

For N=4
Calculation for the chance 4 gets his own seat is an addition of the following chances:
a) prob(person 1 takes seat 2) * prob(N=3) +
b) prob(person 1 takes seat 3) * prob(person 3 takes seat 1).
a) is 1/3 * 1/4. Note that when person 1 takes seat 2 that person 2 basically is in same situation as person 1 was and can be considered the same crazy passenger just with one seat less in the plane.
b) is 1/3 * 1/2. The 1/2 is due that only seat 1 and N are available for passenger 3, since passenger 2 took his own seat.
So prob(4) = 1/3 * 1/4 + 1/3 * 1/2 = 1/4.

Lets do one more before we do the formulae over n.
N = 5
person 5 gets his seat when
a) prob(person 1 takes seat 2) * prob(N=4) +
b) prob(person 1 takes seat 3) * prob(N=3) +
c) prob(person 1 takes seat 4) * prob(person 4 takes seat 1).
Thus prob(5)  is 1/4 * 1/4 + 1/4 * 1/4 + 1/4 * 1/2 = 1/4.

So now for n = N, is
prob(N) = sum(2 <= n <= N-2 of 1/(N-1) * prob(N + 1 - n)) + 1/(N-1) * 1/2 = (N-3)/(N-1) * 1/4 + 1/(N-1) * 2/4 = 1/4. 

I think that what most people seem to forget is that not all permutations have equal probability.

Rogier Wester
Sunday, February 01, 2004

You have done all calculations assuming that person #1 doesn't take his seat. What is given is the fact that person #1 is crazy and he MAY or MAY NOT take his own seat. You have completely ignored the fact that he MAY occupy his own seat. That's why you answer is half of the one proposed earlier.

VikasRana
Monday, February 02, 2004

Ok, so it looks like Marc has the right idea (as well as everyone else who said 1/2).  Although it seems wierd, it is correct.  I had to check it out, so I wrote up a quick C++ program to simulate it using random numbers, and it seems to be normally distributed around .5.  Good work everyone!

Tyler
Wednesday, February 04, 2004

I have learned a lot from you guys. Here I want to consider it from the view of graph. As pointed by Aryabhatta, we can view this problem as a graph problem. Each feasible seating corresponding to a graph with the property that it contains only one cycle that begin form point one, each point on the cycle is smaller then his son, except the last one. We can divide these graphs into two sets: one that includes 100 and the other does not. Then we can see there is a 1-1 correspondence between these two sets: If a cycle does not contain 100, we can insert 100 to get a cycle in the other set and vice versa. In fact for the graph without cycle, that means every one sits on his own seat, we can think the point 1 is a self-cycle, and we can insert 100 to get a cycle, which corresponds to the case that 1 sits on 100 and 100 sits on 1. This shows that there are exactly half cases that 100 sits on 100. So the probability is ½.

shaoji
Tuesday, February 10, 2004

The answer is definitely 1/2

For those of you who don't believe this look at the following

3 people on the plane
1/3 of the time crazy picks his seat (OK)
1/3 of the time he picks #2 seat - then 1 in 2  chance that 2 picks seat 1.
1/3 of the time crazy picks last seat (Bad)

so 1/3 *1 + 1/3*1/2 + 1/3 * 0 = 1/2

OK how about 4 seats:  following the above logic
1/4 * 1 + 1/4 * (1/3 + 1/3*1/2) + 1/4*1/2  + 1/4 * 0

more generally the seat s which crazy picks makes the s-th passenger behave like the crazy person!!!!
(in 4 when crazy picks seat 2 the sub-problem is simply the 3-seated problem)
so if crazy picks seat 25 then the 25th passenger acts crazy (and so on...)

so the solution is simply for each seat i the sum of 1/n times the prob of a crazy person on an 100-i sized plane:

1/n +  1/n * my_seat (n-1) + 1/n * my_seat (n-2) + .... 1/n * my_seat (2)

any programmer can see the nice recursive formula and test this (without any random sim)
a simple recursive (a better one caches values of my_seat[i] as a big speed up)

double my_seat (int num_seats) {
  int i;
  double result = 0.0;

  switch (num_seats) {
    case 1:
        return 0.0; // the nth passenger has no say in where they sit
    case 2:
        return 0.5;  // in a 2-person plane this is obvious
    }
 
  result = 1.0/num_seats;
  for (i = 1; i < num_seats;  i++)
      result += my_seat (i) / num_seats;
    return result;  // could cache this
}

You'll find if you run this for any num_seats you get 0.5

Paul Bethe
Tuesday, February 10, 2004

As a real proof it is two step.

1) as above you can show that  f(n) = 1/n + 1-n * f(n-1) + ... + 1/n(f2)    (f(1) = 0

2) prrof by induction:  We know that f(2) = 1/2  assume from 2-> n that f(i) = 1/2 we need to prove this still holds true for f(n+1)

by (1) we know that f(n+1) = 1/(n+1) + 1/(n+1) * f(n) .+ .1/(n+1) * f(n-1) + ....

but all f from 2->n == 1/2 by assumption.  there are n down to 2 terms each were f = 1/2  so the above reduces to

f(n+1) = 1/(n+1) + 1/(n+1) * (n-1) * 1/2 
        =>  (2 + (n-1)) / ( 2n + 2)  => 1/2

Paul Bethe
Wednesday, February 11, 2004

I think the answer is 1/100.
p(i)=prob that i sits in correct place
p(1)=1/100
p(2)=either first guy chooses correct place OR (first guy does not choose correct place and does not choose 2nd guy's spot)
hence, p(2)=1/100+99/100( 98/99)
p(3)=either first guy chooses correct place OR (first guy does not choose correct place AND(first guy does not pick 3rd guy's spot and second guy does not pick 3rd guy's spot)
hence, p(3)=1/100+99/100(98/99*97/98)

p(i)=1/100+99/100(98/99+....+(100-i)/(100-i+1) )
p(100)=1/100+0=1/100

Shub
Monday, February 16, 2004

The only solution is 50%. All it depends on the seat1 person. Whether he sits in his seat or not? is the only the probability to be considered.

PradeepKumarReddy
Tuesday, February 17, 2004

Why not try to solve it with boolean logic?
------------------------------------------------------
1= passenger in the right seat
0= passenger in the wrong seat
Let us start with 3 persons.
We are interested by the probability for p3 (passenger 3).

passenger
  p1 p2 p3  meaning
    0  0  0  p1->p2->p3->p1
    0  0  1  p1->p2->p1
    0  1  0  p1->p3->p1
    0  1  1  not possible
    1  0  0  not possible
    1  0  1  not possible
    1  1  0  not possible
    1  1  1  all fine
...In this table p3 =1 has probability 2/4 or 50%
=======================
Extending to 4
We are interested by the probability for p4 (passenger 4).

passenger
  p1 p2 p3 p4  meaning
    0  0  0  0  p1->p2->p3->p4->p1
    0  0  0  1  p1->p2->p3->p1
    0  0  1  0  p1->p2->p4->p1
    0  0  1  1  p1->p2->p1
    0  1  0  0  p1->p3->p4->p1
    0  1  0  1  p1->p3->p1
    0  1  1  0  p1->p4->p1
    0  1  1  1  not possible
    1  0  0  0  not possible
    1  0  0  1  not possible
    1  0  1  0  not possible
    1  0  1  1  not possible
    1  1  0  0  not possible
    1  1  0  1  not possible
    1  1  1  0  not possible
    1  1  1  1  all fine

....In this table p3 =1 has probability 4/8 or 50%
===========================
It can easily be extended to 5 (32 entries where 16 are not possible) and shown that it is recursive  5 is built on 4, 6 on 5, etc..
The result will always be 1/2.


daniel f.

daniel f. martin
Tuesday, February 17, 2004

I find it amazing that people who claim the solution is a real number other than 1/2 do not take a couple minutes and work out simple cases to see that they have a flaw in there in logic.

Jeff
Saturday, February 21, 2004

*  Recent Topics

*  Fog Creek Home