Dwarves with hats

Posted in Math by pgadey on 2013/11/13

This afternoon Mike Pawliuk told me the following problem:

A thousand dwarves are wearing standing around wearing red or blue hats. No one can see their own hat and no one can communicate with anyone. Can the dwarves devise a strategy to form a line so that all the red hatted dwarves are on one end, and all the blue hatted dwarves are on the other?

While thinking over the solution, it occurred to me that one can obfuscate the problem as follows:

Consider a group of n dwarves as above. Can the dwarves devise a strategy such that all but a uniformly bounded number of dwarves know the colour of their own hat correctly with absolute certainty?

I can’t see a route to the solution of the second problem that doesn’t go through Mike’s puzzle. This is a terrible case of solution induced blindness. Perhaps someone can point out a more direct solution.

Edit: After some reflection, Mike and I have concluded that this problem is too easy without placing restriction on how the dwarves can move around, since a lot can be encoded by in their movement patterns. It’s very easy to get absolute certainty for all but one dwarf as posed.

For the record, here is another dwarf problem that Michelle Boué told me about when I was an undergrad:

Suppose that three dwarves with red or blue hats are sitting in a circle. They decide on a strategy to guess the colour of their own hat without communicating. They all guess simultaneously. Can they do better than guessing uniformly at random?

Tagged with: , ,