This Riddler puzzle is a classic! Can you save the dwarves from the troll?
A giant troll captures 10 dwarves and locks them up in his cave. That night, he tells them that in the morning he will decide their fate according to the following rules:
- The 10 dwarves will be lined up from shortest to tallest so each dwarf can see all the shorter dwarves in front of him, but cannot see the taller dwarves behind him.
- A white or black dot will be randomly put on top of each dwarf’s head so that no dwarf can see his own dot but they can all see the tops of the heads of all the shorter dwarves.
- Starting with the tallest, each dwarf will be asked the color of his dot.
- If the dwarf answers incorrectly, the troll will kill the dwarf.
- If the dwarf answers correctly, he will be magically, instantly transported to his home far away.
- Each dwarf present can hear the previous answers, but cannot hear whether a dwarf is killed or magically freed.
The dwarves have the night to plan how best to answer. What strategy should be used so the fewest dwarves die, and what is the maximum number of dwarves that can be saved with this strategy?
Extra credit: What if there are only five dwarves?
Here is my solution:
This classic puzzle and is typically referred to as a “hat puzzle” because the standard formulation involves prisoners wearing hats. Each prisoner must determine the colour of their own hat based on the hats they see and what the other prisoners do.
The following solution works no matter how many dwarves there are. Let’s suppose there are $N$ dwarves. It turns out it is possible to save at least $N-1$ of the dwarves. If we’re lucky, we’ll save them all. Here is the strategy:
- The tallest dwarf counts the number black dots he sees ahead of him. He will then say “black” if there are an odd number and “white” if there are an even number. Of course, what the tallest dwarf says has no bearing on the color of his own dot, so the tallest dwarf may die.
- The second tallest dwarf also counts the parity of the dots ahead. If the parity is the same as that indicated by the tallest dwarf, then the second dwarf’s dot must be white. Otherwise, it must be black. The second dwarf utters the color of his own dot.
- The third tallest dwarf also counts the parity of the dots ahead. Based on the first two responses, he can deduce the color of his own dot and will also say the right thing.
- This continues in a similar fashion until everybody is finished. When we’re done, only the tallest dwarf had to take a chance; all others will guess their dot color correctly and survive.
This strategy has the best outcome we could hope for because there is no possible way the tallest dwarf can know the color of his own dot. Indeed, no dwarf can see the tallest dwarf’s dot and we have no prior information on how many dots of each color there are! There is a nice video explaining the solution to this problem here.