Cap Puzzle

Puzzle:
An evil troll once captured a bunch of gnomes and told them, “Tomorrow, I will make you stand in a file, one behind the other, ordered by height such that the tallest gnome can see everybody in front of him. I will place either a white cap or a black 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?

Source:
Another one from Gurmeet's blog

Solution:
Highlight the part between the * symbols for the answer.
* 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 “black” if there are an even number of black hats in front of him, otherwise he says “white”. 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. *

Followup:
What if hats come in 10 different colors?

Thanks to Gurmeet for personally helping me with the solution.

Highlight the part between the * symbols for the answer.
* How about ordering the c colors and allowing the first c-1 gnomes to announce the parity of the lowest c-1 colors among the last n-c+1 gnomes. Parity may be represented by the lowest two colors. The remaining n-c-1 gnomes can then deduce their own hat colors. So, for 10 different colors, maximum 9 gnome have to die.*

Better solution: (By Gaurav Bubna)
Highlight the part between the * symbols for the answer.
* Instead of each guy saying the parity of just one color, he can use the binary representation to announce parity of more than one color at the same time..

since everyone can announce a number between 1-10, the first 4 people would say a number between 0-7 to announce the parity of 3 colors.. This way maximum 4 people need to die.*
Update (12/01/10):
Even Better solution for the followup: (By Gurmeet Singh Manku - IIT Delhi, Stanford, Google Research)
Highlight the part between the * symbols for the answer.
*Let colors be labeled 0 thru c-1. The tallest gnome computes s, the sum of all the numbers he sees. Then he announces the color corresponding to s mod c. All other gnomes can now deduce their own cap colors, one by one!*