Results 1 to 6 of 6

Math Help - probability

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    2

    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)?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by gauravk.newton View Post
    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.
    Last edited by awkward; January 29th 2009 at 08:30 PM. Reason: Found a mistake
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    2

    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. )
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by gauravk.newton View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by awkward View Post
    [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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by gauravk.newton View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: January 21st 2011, 11:47 AM
  2. Replies: 3
    Last Post: May 29th 2010, 07:29 AM
  3. fundamental in probability & convergence with probability 1
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: February 23rd 2010, 09:58 AM
  4. Replies: 1
    Last Post: February 18th 2010, 01:54 AM
  5. Replies: 3
    Last Post: December 15th 2009, 06:30 AM

Search Tags


/mathhelpforum @mathhelpforum