Answer: Hat Puzzle

Since someone finally solved the puzzle, it’s time for the solution. Hint: the person who solved it was a computer scientist.

A reminder of the puzzle:

100 people sit in a circle so they can all see each other, but cannot see themselves. Someone walks around putting hats on their heads. He has 100 bins, each with a different color of hats inside, and he chooses a hat from an arbitrary bin for each person. Multiple people can have hats from the same bin, and not every bin must necessarily be used.

After looking at everyone else’s hats, everyone in the circle must guess the color of their own hat. They can confer beforehand about how they will guess, but cannot communicate after the hats are put on their heads. Describe a strategy so that exactly one person will guess their hat color correctly.

Solution:
Each of the 100 colors gets a number, starting with 0 and ending with 99. Now imagine an outside observer who can see the number of every single hat. If he added them all up and announced the sum, everyone would be able to guess their own number by subtracting the sum of the hats they can see from the true sum to find what’s missing.

This works even if the outside observer announces only the last two digits of the sum, because if, for example, you know the last two digits of the sum of all hats are 23 but the last two digits of the sum of the hats you can see is 75, then your hat must be 48.

Now the answer is evident. Since there is no outside observer, one person in the circle assumes the last two digits of the sum of all the hats are 00. The next person assumes the last two digits are 01. The last person around the circle assumes the last two digits are 99. Exactly one person is making the right assumption, so when everyone guesses their own hat based on their assumption, exactly one guess will be correct.

2 Responses to “Answer: Hat Puzzle”

  1. jon Says:

    But where could you find 100 computer scientists who could differentiate between 100 different colors?

  2. Mark Eichenlaub Says:

    they can do 256^3

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: