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 my point of view, the minimum amount of turns is either 1 or 2, because it states "on each round, each person may choose to either keep the hat they currently have, or swap hats with exactly one other person." then in the first turn N is passed to person number 1, and so on the 2nd turn, number one could choose to swap his hat with no N so that N has the N hat, and then number 1 will have N's old hat (N-1), then (in this egsample N=9) so that number 8 chooses to swap hats with number 1 so that 8 has the hat number 8 (only in the case that N=9) and this continues for each number, each swapping hats with number one in turn, until 1 has his own Hat

Posted by chris on 2005-02-26 06:05:05