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?

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 c_{n} the hat color of the n'th dwarf. Dwarf 1 can see c_{2}, c_{3}, ..., c_{100} and guesses c_{2} + c_{3} + ... + c_{100} out loud as its own color. Now, dwarf 2 sees c_{3}, c_{4}, ..., c_{100} and hears c_{2} + c_{3} + ... + c_{100}, hence he can compute c_{2} as the difference c_{2} = (c_{2} + c_{3} + ... + c_{100}) - c_{3} - ... - c_{100}. In general, dwarf i hears c_{2} + c_{3} + ... + c_{100}, c_{2}, c_{3}, ..., c_{i-1} and sees c_{i+1}, ..., c_{100}, hence it can compute c_{i} as the difference c_{i} = (c_{2} + c_{3} + ... + c_{100}) - c_{2} - ... - c_{i-1} - c_{i+1} - ... - c_{100}.

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!