Fog Creek Software
Discussion Board




crazy guy on airplane

Cute puzzle! Solution is: 1/2. This can be shown by solving the more general problem of finding the probability that the nth passenger gets his assigned seat.

Base step: if there are 2 passengers, the probability that the 2nd passenger gets his seat is clearly 1/2. Induction step: let's suppose that for any k less than n, the probability that in a queue of k passengers the kth gets his seat is 1/2. What, then, is the probability that the nth passenger gets his seat in a queue of n passengers? Let's divide the possibilities into 2: those where the first passenger chooses one of seats 2,3, ..., n-1, and those where the first passenger chooses either seat 1 or seat n. In the second set of possibilities, the remaining passengers sit in their assigned seats, so there are only two possibilities here, and in precisely one of them passenger n gets to sit in his assigned seat. But the first set of possibilities is precisely the set of possibilities where there are n-1 passengers. That is, the first passenger's taking of seat j effectively makes passenger j the first passenger in a size n-1 version of the problem. (Just remove the first passenger and seat j, renumber seats j+1, ..., n to j,j+1, ..., n-1, and move passenger j to the front of the queue!) But it's the induction hypothesis that the probability of passenger n (renumbered as passenger n-1) getting his seat here is 1/2. So if we add two events to the probability space, one in which passenger n gets his seat and one where he does not, the probability remains 1/2.

Adam Vinueza
Tuesday, April 19, 2005

A different way (recursive) to get the solution:

let's call P(k,n) as the probability that passenger k out n needs to choose a seat at random (either because he is the first passenger or because his seat is occupied).

What we are after is the value for P(n,n)

Clearly P(1,n) = 1  (first passanger choose at random)
and
P(2,n) = P(1,n)*1/n  (first passenger will occupy the seat of p2 with prob 1/n)
then
P(3,n) = P(1,n)*1/n + P(2,n)*1/(n-1)  (passenger 2 will occupy seat of p3 with prob 1/n-1, provided that his seat is taken)

generally

P(k,n) = SUM(i= 0...k-2)[P(i+1,n)*1/(n-i)]      k<=n

so

P(n,n) = SUM(i= 0...n-2)[P(i+1,n)*1/(n-i)]  (using the probabilities calculated recursively above)

This yields 0.5 for any value of n

Gualtiero

Gualtiero Chiaia
Monday, April 25, 2005

Just a note on Adam's solution: it's not immediately obvious (at least not to me) that moving passenger j to the front of the queue will not change the probabilities, since the order in which the passengers come in affects which people could potentially be sitting in their seat. The proof in fact requires the strong induction which he hinted at but didn't use: the first passenger's taking of seat j effectively makes passenger j the first passenger in a size n-j+1 version of the problem [not n-1 as is stated] (if crazy guy sits in seat j then passengers 2 through j-1 will all happily sit in their seat, leaving passenger j to choose between seat 1 (where, as in the original problem, if he sits everything else will run smoothly) and seats j+1 through n, which can be renumbered 2 through n-j+1. Of course, because of the strong inductive hypothesis, it still works. And I agree it's a cute problem! Very satisfying indeed.

Chris Harris
Tuesday, April 26, 2005

p.s. sorry for lack of close bracket - made my comment even less comprehensible than it already was.

Chris Harris
Tuesday, April 26, 2005

One way to explain the solution intuitively is to consider what happens every time that a passenger is "bumped" (that is, finds that their assigned seat is already occupied).

If the bumped passenger randomly picks seat #1, then no further passengers will be bumped and passenger #100 will be seated correctly. If, on the other hand, the bumped passenger randomly picks seat #100 then passenger 100 is certain to be bumped because every one up to (but not including) passenger 100 will be seated correctly. If the bumped passenger picks any other seat than another passenger will find themselves bumped and the same observations that held true for the first bumped passenger will hold true for the second and each succeeding bumped passenger (even as the number of open seats declines).

Since the odds of a bumped passenger picking seat #1 are always the same as the odds for picking seat #100, then the odds of passenger 100 being in seat 100 are always even with the odds of passenger 100 being bumped as the plane fills up. Even odds with only two possible outcomes means that odds of one outcome versus the other are the same, or 50/50.

Greg Herlihy
Wednesday, April 27, 2005

Just to complete the recursive solution,

this is a simplification of my resursive solution, as proposed
by Jie Ding and Peter Walsh

--continew from my contribution above---

p(k,n) is the prob that passenger k choose a seat at random.
p(n,n) = SUM(i= 0...n-2)[p(i+1,n)*1/(n-i)].
Each term in the sum series for p(n,n) denotes the prob that passenger n's
seat is occupied by passenger i+1, thus formula is correct. To simplify,
note that p(3,n)-p(2,n)=p(2,n)*1/(n-1) => p(3,n)=p(2,n)*n/(n-1). Generally,
p(k,n)=p(k-1,n)*(n-k+3)/(n-k+2). Hence,
p(n,n)=p(1,n)*[1/n]*[n/(n-1)]*[(n-1)/(n-2)]*...*[3/2]=0.5

Gualtiero

Gualtiero Chiaia
Thursday, May 12, 2005


<b>Answer is 1/2>/b<
<b>Sol:</b>Since all the passengers except the first one will try to occupy their own place, hence when the 100<sup>th</sup> passenger comes in 99 seats must be occupied.
The unoccupied seat can either be 1<sup>st</sup> or 100<sup>th</sup>
Take an example:
Suppose the 1st person takes seat number 30(randomly)
all passengers numbered 2,3,4,5...29 will seat on their respective seats.
Passenger number 30 will again choose a seat at random say 85, all passengers from 31 to 84 will sit on thier respective positions and 85th will choose a seat at random
say 99 .86th to 98 will sit on their respective seats.Now 99th will choose either 1st or the 100th seat(cos only these two seats are left).
So when the last passenger enters either 100th or the 1st seat will be left for him, therefore the probability of him getting his own seat will be 1/2.

manjeetbothra@blogspot.com
Saturday, June 11, 2005

*  Recent Topics

*  Fog Creek Home