# Thoughts of a geek

## 15 August 2013

### Dwarves and hats

Filed under: Maths — Tags: , , , — qwandor @ 6:44 am

Well! I have been meaning to post this for quite some time. Here, at last, are four puzzles involving dwarves and hats.

Puzzle 1, perhaps the easiest:
(I heard this one from Josh Baker when we went for a walk in Otari-Wilton’s Bush earlier this year.)

There are 4 dwarves. A goblin (who hates dwarfs, as all goblins do) has buried them in the ground up to their chins, such that they can see directly in front of themselves but not turn their heads. They are in a straight line, but with a tall wall between dwarves 3 and 4. All the dwarves are facing towards the wall, so dwarf 1 can see dwarves 2 and 3, dwarf 2 can see dwarf 3, and dwarves 3 and 4 can only see the wall. Their tormenter has also put a hat on each dwarf’s head, such that they cannot see their own hat.

He then tells them that he has given two of them red hats and two of them green hats, and that if any one of them calls out his own hat colour he will let them all go free. However, if any of them calls out the wrong hat colour, says anything else, or makes any noise or attempt to signal the others, he will leave them all buried to starve.

Assuming the goblin is telling the truth about the hats he has given them, and will keep his promise, what should the dwarves do?

Puzzle 2, along similar lines and also from Josh, but more difficult:
This time 5 dwarves are buried in the ground, but they are in a circle so that they can all see each other. Again, each has a coloured hat which he cannot see, but this time they can all see all hats but their own.

They are told that they have each been given a hat that is either red, yellow, green, cyan or blue. It may be that they all have different coloured hats, or it may be that some of them (or even all of them) have the same colour. This time they must all call out at once what colour hat they think they are wearing, and if any one of them gets eir colour right then they will all be set free. If they all get the wrong colour they will be left to die. What should they do in this case?

Puzzle number 3 came from Emily:
There are 100 dwarves in prison. They were probably falsely accused of their crimes; it is a hard life being a dwarf, and the justice system is all biased against them. Anyway, they have been in prison for a while, and their jailer is getting bored, so she decides to play a game with them. She takes them all into a room, which contains nothing but a single light hanging from the ceiling, and a lightswitch on the wall to turn it on and off, and explains the rules to them:

“Once you leave this room you will all be put in solitary confinement. I will then bring you back in one by one. When I bring you back you may choose to switch the light on or off, or to leave it as it is. You will then go back to your cell, and I will bring the next dwarf in. I will keep on doing this until one of you tells me that e is sure you have all been brought back at least once. If e is right, then I will let you all go free. If, on the other hand, e is wrong and not all of you have yet been brought back to this room, then I will hang you all. I will bring you in in whatever order I feel like, at whatever speed I feel like, and will keep on doing so until one of you says something. I will not touch the lightswitch.”

She then takes them each to their cells, and begins her game. They all have identical grey prison-issue hats.

a) Assuming that the jailer leaves the light on when they leave the room, so it is on when the first dwarf is brought back in, what should they do?

b) If the dwarves do not know whether the light will be on or off initially, what should they do?

Puzzle number 4 is from Christo’s blog (but do not look there until you have solved it, as there are spoilers):
100 dwarves are in a line, so each can only see the dwarf in front of em. Each is hatted in either magenta or brown. They are told that they must each call out their guess at their own hat colour, but they can do so in any order they choose. If any of them says anything other than a hat colour, speaks more than once, or tries to look around or gesticulate e will be immediately defenestrated. Once they have all made their guesses those who got the right colour will be freed, while those who guessed wrong will be defenestrated.

Dwarves like to work together, so what should they do to minimise defenestration?

Interestingly there at least two quite different approaches to this, so see if you can get them both.

Comment below if you want hints or clarification. If you think you have a solution please email me directly so as not to spoil the puzzles for other people, and I will post a comment to confirm you got it. Feel free to post how many dwarves you think can be saved for puzzle 4 though.

(And yes, for all their flaws, these dwarf-haters do like to use Spivak pronouns.)

[Edit 2013-08-15: Corrected typo in puzzle 2.)