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: Solution by Avin)

Avin,
As I said, I just did some testing (No clever math), just as Federico I noticed that every turn, half of the people could get their hats back.
This works until you have an odd number of wrongly placed hats.  Then you can only continue with one less of what is left. (If you have 13, then continue with 6)  This goes until you get again an odd remaining number where you add the one that is still stuck with a wrong hat.
Example:
Start with 13
Solve 6, 7 left
Solve 3, 4 left
Solve 2
Solve 2
12 = 1101 (4 digits, 4 rounds)

Why N-1 instead of N? Well because of the power 2 numbers:
Start 8
Solve 4
Solve 2
Solve 2
8 = 1000 and 7 = 101 (3 digits, 3 rounds)

I started writing down the numbers in binary and then saw the solution I gave.
I think it is the same as Federico's, except his is a nicer formula, I wish I had thought of base 2 log.

Posted by Hugo on 2005-02-25 16:10:44