Apologies for not posting the answer earlier – I was traveling last weekend.
This was a difficult problem on a relative scale, and I therefore received the correct from all the die hard puzzle solvers in addition to one my friend’s son – Danny, a 14 year old in Washington DC. Other people to send the right answers were Pratik Poddar, Abhinav Jain, Suman Saraf and Prakhar Prakash – well done all!
Those who have not tried it yet – I will highly encourage trying it before reading the answer – it is a beautiful puzzle!
The answer is 1/2. I am giving two explanations, one from Pratik (which I really liked) and the other from Suman (which is the way I did it as well):
From Pratik:
Only one of the two seats can be remaining when the last guy comes – either the seat allocated to the first person or the last person (anything else cannot be there can be easily proved by contradiction)
Now, since for all the people taking the seat after the first person and before the last person, there is no difference between the two seats.
So probability that the last person will get his correct seat is 0.5
From Suman:
At every turn, it is essentially a toss between the first seat and the last. If a person sits in the first seat, the last person gets his own seat. If the person sits in the last seat, the last person has to sit in the first seat. If he sits anywhere else we just defer the decision.
We could also represent this by a recurrence like:
P(n) = 1/n*1 + 1/n*0 + (n-2)/n*P(n-1)
Where P(n) is the probability that the last person sits on his own seat considering n people.
There is 1/n chance of sitting on the first seat (in which case the last guy definitely sits on his own seat)
There is 1/n chance of sitting on the last seat (in which case the last guy definitely doesn’t sit on his own seat)
There is n-2/n chance of sitting somewhere else, in which case the problem continues with a lesser person
P(1) = 1
It follows
P(2) = 1/2
P(3) = 1/2
and so on.
Hope you all enjoyed the puzzle!
Alok Goyal's Puzzles Page 