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?

(fivethirtyeight)

Solution:

The tallest dwarf (#1) will signal with his call whether the number of black dots he sees is odd or even. Suppose he says “black” if odd and “white” if even. Then #2 knows that if the number of black dots he sees differs in parity from those #1 sees, his dot must be black (and same parity, white). He calls his color accordingly, tipping off #3 to whether #2 saw an odd or even number of black dots. And #3 acts identically, as do all until #10, who knows whether #9 saw an odd (1) or even (0) number of black dots, and infers the color of his dot on that basis. So nine of them will survive for sure, with the tallest getting a 50% shot.

The “Extra credit” question seems to be a red herring, as there is no difference in the required approach.