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.

### Like this:

Like Loading...

*Related*

This entry was posted on July 22, 2010 at 10:52 am and is filed under problems and solutions. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

July 22, 2010 at 12:48 pm

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

July 22, 2010 at 4:18 pm

they can do 256^3