Wizards and Dwarves

I wrote about interview puzzle questions recently to set the context for this article.

A few years back, a colleague asked me to ponder a Wizards and Dwarves puzzle as a potential interview question.  A typical statement goes something like this:

A village of wizards is nearby a village of dwarves.  Once a year, the wizards visit the dwarves, and line up the dwarves in increasing order of height, so that each dwarf can only see the dwarves smaller than himself.

The wizards have white and black hats.  They place a white or black hat on the head of each dwarf (using a strategy of their choosing, perhaps even randomly).  Then starting at the back of the line (the tallest dwarf), they ask each what color hat he is wearing. 

Each dwarf who answers incorrectly is killed by the wizards.  The other dwarves can hear his answer, but do not know whether he was killed.

What strategy minimizes the number of dwarves killed?

Ok, I thought about it.

Pondering

Among many irritations I have for puzzle questions, the fiction is frequently distracting: 

Why villages?  Why wizards and dwarves?  Why in order of height?  What if they are all of the same height?  How can you kill a dwarf and not have his neighbor nearby hear it?

And my brain spins with other tangents:

Dwarves have high magic resistance and constitution – don’t they get a saving throw?  Toss in a few +5 battle axes and there would be a wizard slaughter!

Meh.

Wizards, Dwarves and Barometers

In the spirit of the barometer question, I formulated the following responses:

• Non-violent non-cooperation.  It is not stated that there is a penalty for non-cooperation.  In the spirit of Gandhi, the dwarves refuse to be sorted by height, do not line up, and will not wear hats.  Wizards are known weaklings and will be unable to forcefully move the dwarves into place.
• Scatter.  The dwarves split their village up into smaller villages, until each village consists of a single dwarf.  Each dwarf now has an equal chance of survival (this strategy, while fair, will be popular with the tall dwarves, but less so with the short ones).  The maximum number of dwarves killed will always be one.
• UN Convention on Genocide.  The dwarves are being unfairly singled out as a group for destruction.  Citing Resolution 260 (III), they appeal to the United Nations and await protracted discussion.
• Mini-guns.  Despite their diminutive size and desire peace, the dwarves obtain special weapons training, obtain mini-guns and when threatened, and whoop some major wizard ass.
• Mobile Phone.  First variant – dwarf uses a mobile phone to take a picture of his hat, revealing the color.  Second variant – dwarf snaps a photo of the dwarf in front of him and texts it to him.
• Low tech (no mobile phone required).  Dwarf turns around and asks the dwarf behind him the color of his hat.
• Vacation.  The wizards arrive once a year.  The dwarves arrange to be out of town on that day (ideally somewhere warm and sunny).
• Insubordination.  Each dwarf takes off his hat and reports its color.

And so on.

Conclusion

If you follow the intended script, you can find solutions in which no more than one dwarf is killed (the tallest has no knowledge of his hat color and his odds are essentially subject to chance).

But as shown above, one can simplify and further optimize the solution by exploiting ambiguities in the fiction.

And it’s a lot more entertaining.