Fog Creek Software
Discussion Board




crazy guy answer

I'll start with a warm-up question: If passenger 100 finds seat 100 occupied, which seat will he have to sit in?




....




Crazy passenger 1 either sits in seat 1, which means no one else is displaced from their seat, or he sits in seat N, displacing passenger N. In which case passenger N either sits in seat 1, which is still open, and no one else gets displaced, or he sits in seat M, displacing passenger M (M>N). Eventually when we get to passenger 100, either someone has sat in seat 1, leaving the rest of the passengers undisturbed, or passenger 100 will have to sit in seat 1.


So, returning to the original question, what are the probabilities? This looks like another by-induction kind of problem.  Call the probability that passenger N sits in a different seat than his own, P(N).

P(1) = 99/100, since 1% of the time passenger 1 will sit in his own seat by dumb luck.

P(2) = 1/100, since passenger 1 sits in seat 2 1/100 of the time. If he is displaced, Mr. 2 has 99 remaining seats to choose from.

P(3) = 1/100 + (1/100)/99, since passenger 1 takes Mr. 3's seat 1/100 of the time, and there's an additional chance that passenger 2 took Mr. 3's seat if he was displaced by passenger 1.

Actually, at this point we can generalize:

P(n) = P(n-1) + p(n-1)/(102-n). Each passenger is just as likely to be displaced as the previous one, plus the small probability that the previous passenger was displaced into the next seat.

We can rewrite this as a product

P(100) = 1/100 * Pi(1+1/(102-i), i, 3, 100),

using the notation of my TI-92, which gives back the answer

P(100) = 0.5.

So the answer is, passenger 100 finds his seat displaced exactly half of the time.  That seems like too "clean" of an answer for too much computation... Was there a trick I missed?

Okay, it's not hard to work it out by hand either...

P(100) = 1/100 * Pi(1+1/(102-i), i, 3, 100)

P(100) = 1/100 * Pi((j+1)/j), j, 2, 98)

P(100) = 100!/(2*100!) = 1/2

but I'm still missing the "aha..." I notice that the answer works out to 1/2 for the last passenger no matter how many passengers are on the plane, which is interesting.

Peter Meilstrup
Thursday, April 10, 2003

an "easier" solution is to consider what happens if there are n passengers and n seats.

1) Passenger 1 always sits in the correct seat
2) There is a 1/2 chance that passenger 2 sits in seat 2. As there are only two possibilities, each with equal probability.

1,2
2,1

3) There are 4 possibilities,

1,2,3  with 1/3 probability of occurring
3,2,1  with 1/3 probability of occurring

2,1,3  with 1/6 probability of occurring
3,1,2  with 1/6 probability of occurring

Clearly Passenger 3 is in seat 3 with 1/2 probability


Now think about k passengers and seats.

k) There is some even number [2^(k-1) to be exact] of different possibilities all with different probabilities. For example there is a 1/k chance that the order is 1,2,3,..., k.

Now the trick is to realise that these possibilities form pairs one with passenger k in seat 1 and one with passenger k in seat k, both possibilities with equal probability. The pairs being identical except that the occupants of seats 1 and k are swapped.

Call the other passenger at the start and end such pair "a" so the sequences look like

a, ... , k
k, ... , a

Now when a sits in seat 1 or seat k there is an equal probability that he/she chooses either one. In either case all the passenger between a and k will sit in their correct seats.

From this it is clear to see that passenger k has a 50% chance of sitting in his/her own seat.

Alan Riddell
Saturday, April 19, 2003

I came to the same 50% answer.

Lets assume that the 99th guy was displaced from his seat.  He will have two seats to choose from 1 or 100.  1 is still not occupied because that would close the loop and 100 cannot be occupied because then the 99th guy would not be displaced.  The 99th guy has 1 out of 2 chances of displacing the 100th guy's seat.

Jonathan Hager
Wednesday, May 14, 2003

Yet another look at it:
Every Passenger has a certain probability of having his place taken. we can mark this probability as P(k).
The seat K was taken only if person 1 took a seat between
2 and K.
Therefore for sure seat 1 is vacant and seat 100 is vacant.
Now the partial probability that seat #100 is taken by person K is: P(k)*1/(N-K).
And the partial probability that seat #100 stays vacant ( by taking #1 instead) is also: P(k)*1/(N-k).
Person K may also take a seat of person L ( L>K & L<100).
But this contribution will add up P(L) or the probability of Seat L being siezed.
Therefore if we sum the the contributions to the probability
of having seat 100 taken and having seat 100 stay vacant,
it adds up to the same values and the sum of it must be 1.
therefore P(k=100) = P(k!=100) = 1/2.

Aharon Tam
Tuesday, July 08, 2003

*  Recent Topics

*  Fog Creek Home