Try working out some smaller cases first, e.g. 2, 3, or 4 seats and people.
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?
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
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)?
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