At a party with N people, each person is identified by a unique number between 1 and N. Each person is also wearing a hat with their number on it. They decide to play a game. Each person passes his or her hat to the person with the next highest number (so person 2 gets hat 1, person 3 gets hat 2, and person 1 gets hat N). The game proceeds from there in rounds; on each round, each person may choose to either keep the hat they currently have, or swap hats with exactly one other person.

What is the minimum number of rounds, as a function of N, that it would take for every person to get their own hat back? Note: each person can see their own hat at any time.

(In reply to re(2): Solution by Hugo)

Ok, I was mistaken in my first post - you can indeed do better than that. This was the first solution I came up with myself, but look at all the wasted opportunities for swapping! If the party members followed this solution, all of them would participate in the first round, but only half of them would participate in the second. Only a quarter would participate in the third round, etc. What if you could optimize the rounds to minimize the number of people who were "sitting out" of each round?

Posted by Avin on 2005-02-26 02:51:48