A dwarf-killing giant lines up 10 dwarfs from shortest to tallest.
Each dwarf can see all the shortest dwarfs in front of him, but cannot see the dwarfs behind himself.
The giant randomly puts a white or black hat on each dwarf. No dwarf can see their own hat. The giant tells all the dwarfs that he will ask each dwarf, starting with the tallest, for the color of his hat.
If the dwarf answers incorrectly, the giant will kill the dwarf.
Each dwarf can hear the previous answers, but cannot hear when a dwarf is killed.
The dwarves are given an opportunity to collude before the hats are distributed.
What strategy should be used to kill the fewest dwarfs, and what is the minimum number of dwarfs that can be saved with this strategy?
My approach:
1st guy counts which color is max, says it, all others copy his ans. This way, we save at least 5, but I think we can optimize this, just can't figure out how….
Best Answer
Parity: Dwarves agree that black = 1 and white = 0. First dwarf adds up all the hats he sees mod 2 and calls that out. The rest of the dwarves need to rememeber this. Each dwarf adds up the hats he sees mod 2 and if it's the same, considers his hat white, if it's not the same parity, then he considers his hat black.
After that each dwarf in turn calls out his presumption of hat color, except that the listening dwarves must change their guess each time someone before them calls "black" (after the first dwarf). That way they only have to add up the hats once, and do not need to remember each call, only to change their color when "black" is called.
All dwarves but the first are guarenteed to survive.