perplexus.info :: Algorithms : Hat Exchange

Hat Exchange (Posted on 2005-02-24)

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.

Submitted by Avin

Rating: 3.0000 (5 votes)

Solution: (Hide)

Two rounds.
On the first round, each person k swaps hats with person N-k+1 (so person 1 swaps with person N, person 2 swaps with person N-1, etc.) If N is odd, the person in the middle keeps the hat they have.
On the second round, person 1 already has their own hat, so they keep it, and every other person k swaps with person N-k+2 (so person 2 with person N, 3 with N-1, etc.). If N is even, then person N/2 + 1 does not swap.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
re(4): Solution	Ffaada	2024-09-23 13:51:25
re: Better Solution (spoiler)	Hugo	2005-02-26 19:12:54
answer(in my eyes)	chris	2005-02-26 06:05:05
Better Solution (spoiler)	Tristan	2005-02-26 03:01:46
re(3): Solution	Avin	2005-02-26 02:51:48
re(2): Solution	Hugo	2005-02-25 16:10:44
re: Solution	Avin	2005-02-25 13:15:10
Maximum	Federico Kereki	2005-02-24 15:34:05
Solution	Hugo	2005-02-24 15:21:26

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info