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