Problem 05

Problem 05

A giant has captured 100 dwarfs, and plays game with them. He puts each dwarf a hat on, colored in one of k ≥ 2 different colors. He puts them in a long row, so that each dwarf sees only the dwarfs in front of them in the row. In turn, starting from the back of the row to the front, they can guess their hat color out loud (so that all dwarfs hear it). Wrong guesses lead to death, good guesses leed to freedom. If they are allowed to agree on a strategy, how many dwarfs can be saved for sure?

Solution

The first dwarf in the back of the row has no info and hence has to guess, so we can at most save 99 dwarfs.

More surprising is that we can actually save 99. A possible strategy is as follows. Number the colors by the remainder classes 0, 1, ..., k-1 modulo k and denote by cn the hat color of the n'th dwarf. Dwarf 1 can see c2, c3, ..., c100 and guesses c2 + c3 + ... + c100 out loud as its own color. Now, dwarf 2 sees c3, c4, ..., c100 and hears c2 + c3 + ... + c100, hence he can compute c2 as the difference c2 = (c2 + c3 + ... + c100) - c3 - ... - c100. In general, dwarf i hears c2 + c3 + ... + c100, c2, c3, ..., ci-1 and sees ci+1, ..., c100, hence it can compute ci as the difference ci = (c2 + c3 + ... + c100) - c2 - ... - ci-1 - ci+1 - ... - c100.

Remarks

Students love this puzzle and work on it during the entire lecture (even while I'm expecting them to do other exercises). They usually don't manage to solve it, but they have fun trying, and they are amazed by the solution and how modular arithmetic pops up at the most unexpected places. And the moral of the story: modular arithmetic can save your life!