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

Related post : here, here and here

 

Advertisements

Tags: , ,

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

  1. Pratik Poddar Says:

    Elegant indeed! Thanks 🙂

  2. Puzzle : Black and White hats! « Me, Myself and Mathematics Says:

    […] posts : here, here, here and […]

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: