# probability

• Jan 29th 2009, 12:50 AM
gauravk.newton
probability
A line of 100 airline passengers is waiting to board an aeroplane. They each have a ticket to one of the 100 seats of that flight. (For convenience, let's suppose that the kth passenger in the line has a ticket for the seat number k.)
Unfortunately, the first person in line of these 100 passengers is crazy, and will ignore the seat number on the ticket, picking up a random seat to occupy. All the other 99 passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, then they will search for a free seat to sit in, at random.
What is the probability that the last (100th) person in the line to board the plane will sit in his/her proper seat (#100)?
• Jan 29th 2009, 05:55 PM
awkward
Quote:

Originally Posted by gauravk.newton
A line of 100 airline passengers is waiting to board an aeroplane. They each have a ticket to one of the 100 seats of that flight. (For convenience, let's suppose that the kth passenger in the line has a ticket for the seat number k.)
Unfortunately, the first person in line of these 100 passengers is crazy, and will ignore the seat number on the ticket, picking up a random seat to occupy. All the other 99 passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, then they will search for a free seat to sit in, at random.
What is the probability that the last (100th) person in the line to board the plane will sit in his/her proper seat (#100)?

Hi gauravk.newton,

More generally, let's say P(n) is the probability that the last passenger gets his desired seat on an n-seat airplane. Working out P(n) for a few small values of n, we begin to suspect P(n) = 1/2 for all $n \geq 2$. Let's see if we can give a proof by induction on n.

The case n=2 is easy. The first passenger chooses seat 1 with probability 1/2, in which case passenger 2 gets his desired seat. Otherwise passenger 1 chooses seat 2 and passenger 2 is unhappy. So P(2) = 1/2.

Now assume that P(n) = 1 for all n such that $2 \leq n \leq k$, for some $k \geq 2$. Suppose we have a k+1 - seat airplane.

With probability 1/(k+1), the first passenger picks seat 1 and everyone (including the last passenger) gets his desired seat.

Also with probability 1/(k+1), the first pasenger picks seat k+1 and the last passenger does not get his desired seat.

With probability (k-1)/(k+1), the first passenger picks seat number s, where $2 \leq s \leq k$. Then passengers 2, 3, ..., s-1 will all take their desired seats and passenger s will make a random choice from the remaining k-s+2 seats. This is just like the original problem, where passenge s now takes the place of passenger 1 and the plane contains k-s+2 seats. By the inductive hypothesis, the probability that the last passenger will get his desired seat is 1/2.
[Edit: No, this part isn't quite right-- let me work on it and get back to you later. It's too late at night to work on it now.]

So $P(k+1) = \frac{1}{k+1} \cdot 1 + \frac{1}{k+1} \cdot 0 + \frac{k-1}{k+1} \cdot \frac{1}{2} = \frac{1}{2}$.

This completes the proof.
• Jan 30th 2009, 12:10 AM
gauravk.newton
Thanks
But I would look forward for a more general solution. I hate mathematical induction. It isnt mathematics actually, just got the problem amidst a collection of puzzles.

PLEASE CAN I GET THE REPLIES??
(I joined this forum just for this question and that too with high hopes. Hope you people don't disappoint me. )
• Jan 30th 2009, 01:14 AM
mr fantastic
Quote:

Originally Posted by gauravk.newton
But I would look forward for a more general solution. I hate mathematical induction. It isnt mathematics actually, just got the problem amidst a collection of puzzles.

PLEASE CAN I GET THE REPLIES??
(I joined this forum just for this question and that too with high hopes. Hope you people don't disappoint me. )

This is a less than grateful response to an excellent reply. I doubt you will get a better reply.

Proof by induction is a valid mathematical proof and is a standard method of proof in many probability problems. You will have to accept that fact. My advice is to make it part of your arsenal.
• Jan 30th 2009, 01:58 PM
awkward
Quote:

Originally Posted by awkward
[snip]

With probability (k-1)/(k+1), the first passenger picks seat number s, where $2 \leq s \leq k$. Then passengers 2, 3, ..., s-1 will all take their desired seats and passenger s will make a random choice from the remaining k-s+2 seats. This is just like the original problem, where passenge s now takes the place of passenger 1 and the plane contains k-s+2 seats. By the inductive hypothesis, the probability that the last passenger will get his desired seat is 1/2.
[Edit: No, this part isn't quite right-- let me work on it and get back to you later. It's too late at night to work on it now.]

Late last night I thought I had found a mistake in the above, but having thought about it more I now think I was right all along.

However, the statement "This is just like the original problem, where passenger s now takes the place of passenger 1 and the plane contains k-s+2 seats." may not be obvious. So here is some additional explanation.

When passenger s enter the plane, seat 1 and seats s+1 through k+1 (k-s+2 seats in all) are open and all the others are taken. So he may take seat 1 (in which case all the remaining passengers get their preferred seats), or one of the other k-s+1 seats, where he will sooner or later obstruct another passenger. All seats are equally likely to be chosen.

By way of comparison, consider the first (insane) passenger entering a k-s+2 seat plane. He may sit in seat 1 (in which case all the passengers get to take their preferred seats), or he may sit in one of the other k-s+1 seats, where he will eventually obstruct another passenger. All seats are equally likely to be chosen.

The probabilistic analysis of these two cases is exactly the same, so the last passenger has the same probability of getting his preferred seat in both cases. By the inductive hypothesis, this is P(k-s+2) = 1/2.
• Jan 30th 2009, 02:07 PM
awkward
Quote:

Originally Posted by gauravk.newton
But I would look forward for a more general solution. I hate mathematical induction. It isnt mathematics actually, just got the problem amidst a collection of puzzles.

PLEASE CAN I GET THE REPLIES??
(I joined this forum just for this question and that too with high hopes. Hope you people don't disappoint me. )

I'm not sure what you mean by "a more general solution". After all, we have solved the more general problem of an n-seat plane where the original problem only asked for the case n=100.

And I agree with Mr. Fantastic that you should not be prejudiced against mathematical induction. But if you don't like induction, here is another way to look at the solution. You know the answer for the case n=2: 1/2. Knowing that, you can find the answer for the case n=3. Surprisingly, it turns out to be 1/2 again. Knowing the answer to these two cases you can work on the case n=4. Using the answers to cases 2 and 3 you are able to solve case 4: 1/2 again! ... (dot dot dot)

Mathematical induction is just the mathematically rigorous way to fill in the dots.