Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 07 Jun '08 04:53 / 1 edit
    Due to the stimulating questions here, this question might have been posted earlier. Sorry if it has. Also this question involves an airplane. I just used the word "plane" for the alliteration.

    There are 100 people on a plane. Let's label them Persons 1-100. The order the people sit down is determined by his or her seat number. There are 100 seats, labeled Seats 1-100. Person 1 does not know where to sit and will sit in any random passenger seat. Persons 2-100 are assigned to their corresponding seat number and will sit there. If someone is already sitting at the assigned seat, the person would sit at a random unoccupied passenger seat. Here's an example:

    Person 1 sits in seat 5
    Person 2 sits in Seat 2
    Person 3 sits in Seat 3
    Person 4 sits in Seat 4
    Person 5 sits in Seat 7
    Person 6 sits in Seat 6
    Person 7 sits in Seat 1
    ...

    This is just one example of what might happen. The question is: What is the probability that Person 100 sits in Seat 100?

    If there are any unclear parts please feel free to ask. I doubt i have left anything out, but if I did, please feel free to say so.

    If this isn't solved by tomorrow, I'll give a hint.
  2. 07 Jun '08 08:35
    Let p(n) be the probability that the last person will sit in the last seat if there are n seats and people.

    First calculate:
    p(2)=1/2
    p(3)=1/2
    p(4)=1/2
    p(5)=1/2
    Hm... I notice a pattern. Proveable by strong induction, or whatever it's called. Unless of course, I'm completely wrong.
  3. Standard member wolfgang59
    Infidel
    07 Jun '08 09:30
    OK.
    Lets call the probability of someone sitting in the nth seat on an n-seater plane P(n)

    For n=2
    P(2) = 1/2 (the first guy either takes seat 1 or seat 2)

    For n=3
    P(3) = the chance of first guy sitting in seat + chance of first guy NOT sitting in seat x 2seater scenario

    Therefore
    P(3) = 1/3 + 2/3 * P(2)
    = 1/3 + 1/3
    = 2/3

    P(4) = 1/4 + 3/4 * P(3)
    = 1/4 + 2/4
    = 3/4

    P(n) = 1/n + (n-1)/n * P(n-1)

    P(n) = (n-1)/n

    So for our 100 seater plane the chances of holder of ticket 100 getting his seat is 1/100.

    Which is surprising .. so I could be wrong!
  4. 07 Jun '08 10:04
    chance of seat being taken:

    P(2) = 1/2
    P(3) = 1/3 + 1/3 x 1/2 = 1/2
    P(4) = 1/4 + 1/4 x 1/3 + (1/4 + 1/4 x 1/3) x 1/2 = 1/2
    p(5) = 1/5 + 1/5 x 1/4 + (1/5 + 1/5 x 1/4) x 1/3 + (1/5 + 1/5 x 1/4 + (1/5 + 1/5 x 1/4) x 1/3) * 1/2 = 1/2
    p(n) = 1/n + 1/n x 1/(n-1) + (1/n + 1/n x 1/(n-1)) x 1/(n-2)...
    = 1/n + 1/(n^2-n) + 1/(n^3-3n^2+2n)

    This may help someone.
    The answer's 1/2, but I can't quite prove it.
  5. 07 Jun '08 10:31
    Ok, so we wish to calculate p(n)
    Let's look at the first guy. If he takes seat 1 or seat n, we get probability of 1 and 0 respectively.

    If he takes seat 2, then we have the n-1 seat scenario, because then person 2 has to choose randomly between n-1 seats, and the fact that every seat (except for 1) has been increased by one makes no difference, because so has the numbers of the people.

    If he takes seat 3, then person 2 takes seat 2, and person three has to choose between n-2 seats, with the seats and people all having their numbers increased by two, thus making no difference.

    Continuing in this fashion, we get that np(n) = 1 + 0 + p(2) + p(3) + ... p(n-2) + p(n-1). Clearly true by strong induction.

    I invite some one to poke holes in my proof.
  6. Standard member TheMaster37
    Kupikupopo!
    07 Jun '08 15:16 / 2 edits
    Originally posted by wolfgang59
    OK.
    Lets call the probability of someone sitting in the nth seat on an n-seater plane P(n)

    For n=2
    P(2) = 1/2 (the first guy either takes seat 1 or seat 2)

    For n=3
    P(3) = the chance of first guy sitting in seat + chance of first guy NOT sitting in seat x 2seater scenario

    Therefore
    P(3) = 1/3 + 2/3 * P(2)
    = 1/3 + 1/3
    = 2/3

    P ...[text shortened]... holder of ticket 100 getting his seat is 1/100.

    Which is surprising .. so I could be wrong!
    Sorry to say this, but indeed you are:

    The calculation for P(3) should be

    P(3) = 1/3 + 1/3 * P(2)
    = 1/3 + 1/6
    = 1/2

    By using 2/3 you forgot that half of that chance is when person 1 sits in seat 3. In that case, person 3 obviously cannot sit in seat 3 anymore.

    If you change that in your proof along with the identical mistakes in the other P(m)'s your proof will become a valid proof for P(n) = 1/2 for all n.
  7. Standard member TheMaster37
    Kupikupopo!
    07 Jun '08 15:21
    Originally posted by Dejection
    Ok, so we wish to calculate p(n)
    Let's look at the first guy. If he takes seat 1 or seat n, we get probability of 1 and 0 respectively.

    If he takes seat 2, then we have the n-1 seat scenario, because then person 2 has to choose randomly between n-1 seats, and the fact that every seat (except for 1) has been increased by one makes no difference, because ...[text shortened]... -2) + p(n-1). Clearly true by strong induction.

    I invite some one to poke holes in my proof.
    Sorry, but I can't find any holes
  8. 07 Jun '08 15:24
    Why not let person 100 enter the plane first, rather than last? He takes a seat in a random way. The probability that he take the seat #100 is 1 of 100. So the probability is 0.01.

    What the others do does not have any bearing at all.
  9. Standard member wolfgang59
    Infidel
    07 Jun '08 17:05
    Originally posted by TheMaster37
    Sorry to say this, but indeed you are:

    The calculation for P(3) should be

    P(3) = 1/3 + [b]1
    /3 * P(2)
    = 1/3 + 1/6
    = 1/2

    By using 2/3 you forgot that half of that chance is when person 1 sits in seat 3. In that case, person 3 obviously cannot sit in seat 3 anymore.

    If you change that in your proof along with th ...[text shortened]... cal mistakes in the other P(m)'s your proof will become a valid proof for P(n) = 1/2 for all n.[/b]
    I was calculating P(3) as a 1 in 3 chance he took seat 3 and a 2 in 3 chance he did not.

    My solution may be wrong but that is not the flaw.
  10. 07 Jun '08 17:15
    If giy 100 went on first then the odds of him sitting in
    the correct seat are 100/1.
    But 99 people are going on ahead of him - so is it 9900/1
    that he will get his seat by chance.
  11. 07 Jun '08 17:20
    That doesn't sound right, it's a far cry from the 1/2 that i got.
  12. 07 Jun '08 17:32
    greenpawn is correct IF they all choose at random, and more than one person can sit in a seat, and then everyone that isn't in seat 100 is put in seat 100 and anyone on seat 100 is killed, then the 100th person picks randomly.

    With the original stipulation, dejection is correct.
  13. 07 Jun '08 21:53
    Been thinking about this.

    When the first guy gets on the plane it's 100/1 he
    will sit in seat No.100

    When the 2nd guy gets on it will be 99/1
    When the 3rd guy gets on it will be 98/1 and so on...

    So you do a factorial of 100 (99+98+97+96.....)and add 1.
  14. 08 Jun '08 01:01
    Originally posted by greenpawn34
    Been thinking about this.

    When the first guy gets on the plane it's 100/1 he
    will sit in seat No.100

    When the 2nd guy gets on it will be 99/1
    When the 3rd guy gets on it will be 98/1 and so on...

    So you do a factorial of 100 (99+98+97+96.....)and add 1.
    Not quite. The only time the second person will not sit in seat 2 is if person one sat in seat 2.

    This means the probability of person 2 sitting in seat 100:

    P(2|S100) = (1/100) * (1/99)
  15. 08 Jun '08 03:50 / 1 edit
    This problem is very simple. At any given time, we are only dealing with only one person displaced at a time, everyone else will take their proper seat.

    Now one of two things will happen eventually.

    If the displaced person takes the first seat, then everyone else will be able to take their own seat, including the last person.

    If the displaced person takes the last seat, then clearly the last person won't be able to, but will have to take the first person's seat.

    If the displaced person takes any other seat, then the decision is passed to the person whose seat was taken, so that one of the top two WILL happen.

    So we are only interested in which seat is taken first, Seat #1, or Seat #100. And since there is no reason to assume either is more likely, that makes it a 50/50 chance.

    EDIT: The first person is considered "displaced" for purposes of analysis, as if he chooses either significant seat, then we know how it all ends.