Puzzle : Coloured Hats and Wizards!

Taking this puzzle from Pratik’s blog.

Problem : There are n wizards in a Kingdom. To test their intellect, the king summons them all. He tells them that on the next day, a hat of a random color from a set of k colors will be put on each of their head. A wizard can look at the colors of others hat but not at his own. He also tells them, that there are k rooms adjacent to the hall in which they will be gathered. Two wizard with the same colored hat must go to the same room, and any two with the different colored hat must go the the different room. One mistake and they all will be executed. What strategy should they come up with?

Solution : Well, the puzzle is not very different from usual black and white colored hats. And hence, the solution I posted as a comment on his blog, though correct, is not efficient. The solution proposed by me is as follows.

Give an ordering to each color $C_1 \dots C_k$ . Now, assume two partitions, $C_1$ and the rest $C_2 \dots C_k$ . Now, it reduces to the normal black and white colored hat puzzle. All wizards with hats colored $C_1$ will be able to figure out in time $O(C_1)$ . Now, they will pick a room. Now, rest of the wizards can again use the partition $C_2$ v/s $C_3 \dots C_k$ as black and white puzzle, and all wizards with $C_2$ colored hats can figure out the color of their hat. And so on.

The solution is an overkill though. Nowhere, in the problem is it mentioned that wizards need to figure out the color of their hat. Merely, partitioning themselves, so that wizards with the same hats are in the same room and with different colored hats are in different room suffices.

So the efficient solution, as posted by a person named Sid, on his blog is as follows.

Give each color a number from $0 \dots k-1$ . Now, each wizard will sum up the colors that he sees in modulo k.

It is trivial to see that two wizard having the same color, will calculate the same number s modulo k. And those with different color will calculate different numbers. That’s it!! Very elegant solution

– Saurabh Joshi

2 Responses to “Puzzle : Coloured Hats and Wizards!”

Pratik Poddar Says:
August 27, 2010 at 12:16 pm | Reply
Elegant indeed! Thanks
Puzzle : Black and White hats! « Me, Myself and Mathematics Says:
January 3, 2011 at 9:00 am | Reply
[...] posts : here, here, here and [...]

Me, Myself and Mathematics