Results 1 to 6 of 6

Math Help - Seating Problem - Any ideas?

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1

    Seating Problem - Any ideas?

    There are seats numbered 1 to 100.
    There are people numbered 1 to 100.

    They take the seats in the order of their number. A person numbered 'i' is assigned seat number 'i'.

    Person #1 is drunk - so he takes any seat at random.
    Rest everyone takes his/her seat, if empty else picks a random seat from the available free seats.

    Q: What is probability that person#100 sits on his assigned seat?

    I haven't been able to make much progress here. Any hints plz?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Try working out some smaller cases first, e.g. 2, 3, or 4 seats and people.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Thanks a lot !

    Infact I could derive a recurrence here

    Let 'n' be number of people

    Then P(n) = 1/n [1+P(2)+P(3)+......+P(n-1)], where P(i) is the Probability that last man gets his seat given there are 'i' people in total.

    P(2) = 1/2 [This can be worked out easily]
    => P(3) = 1/2 and we can see P(n) = 1/2
    Thanks !

    But any better way to solve the recurrence I wrote (without the intution that try to prove the claim than P(n) = 1/2 using the induction)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    But any better way to solve the recurrence I wrote (without the intution that try to prove the claim than P(n) = 1/2 using the induction)?
    I think this problem is usually given in terms of seating on an airplane. Maybe the scenario was changed on purpose to discourage internet searches.

    After some effort, I managed to track down the site where I originally saw this problem! And the non-recursion/non-induction solution is pretty slick..

    Two Math Riddles Combinatorics and more
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    But obviously I failed in my attemp to disguise
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    But obviously I failed in my attemp to disguise
    Haha, I thought maybe it was changed by the person who gave you the problem, didn't think of the possibility that you changed it. I had an unfair advantage because I'd seen the problem and solution already in the last couple months, so it was still relatively fresh in my memory.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Seating arrangements problem
    Posted in the Statistics Forum
    Replies: 0
    Last Post: November 8th 2009, 04:08 PM
  2. Replies: 1
    Last Post: February 6th 2009, 10:11 PM
  3. Committee Seating permutation problem
    Posted in the Statistics Forum
    Replies: 1
    Last Post: June 16th 2008, 05:00 PM
  4. Seating Arrangement Problem
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: December 4th 2007, 12:45 PM
  5. seating problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 20th 2007, 05:17 PM

Search Tags


/mathhelpforum @mathhelpforum