Source: Asked to me by Sudeep Kamath (Third year PhD Student, UC at Berkeley, EE IITB Alumnus)
There are n men, n hats, one hat belonging to each person. A random permutation of hats is picked by the men, whoever gets their own hat, takes it and leaves and a random permutation of the remaining hats is picked and so on. What is the expected number of rounds it takes for everyone to
Hint: Answer is n
Update (21 Oct 2010):
Solution posted by Siddhant Agarwal (Senior Undergraduate, EE, IITB), and a more detailed explanation posted by me in comments!