# Thread: Seating Problem - Any ideas?

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?

2. Try working out some smaller cases first, e.g. 2, 3, or 4 seats and people.

3. 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)?

4. Originally Posted by aman_cc
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

5. But obviously I failed in my attemp to disguise

6. Originally Posted by aman_cc
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.