An evil troll once captured a bunch of gnomes and told them, "Tomorrow, I will make you stand in a file, ordered by height such that a gnome can see exactly those gnomes that are shorter than him. I will place either a red cap or a blue cap on each head. Then, starting from the tallest, each gnome has to declare aloud what he thinks the color of his own cap is. In the end, those who were correct will be spared; others will be eaten, silently." The gnomes set thinking and came up with a strategy. How many of them survived?

Asked during an interview for an internship at a startup in 2000.

There is no way for the tallest gnome to figure out the color of his own hat. However, all others can be saved! The tallest gnome says aloud "blue" if there are an even number of blue hats in front of him, otherwise he says "red". The second tallest gnome can now deduce his hat color. He says it aloud. One by one, all others can deduce their own hat color and say it aloud.

What if hats come in 10 different colors?