I came across this interesting variant of the typical hat problem, in which people are supposed to guess if their hat is black or white:
A king decides to give 100 of his wise men a test. The wise men will stand in line, one behind the other, so that the last person in the line sees everyone else. The king has 101 hats, each of a different color, and the wise men know all the colors. The king puts all but one of the hats on the wise men. The wise men can only see the colors of the hats on people in front of them. Then, in any order they want, each wise man guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the wise men cannot speak. Furthermore, they are not allowed to repeat a color that was already announced. Each wise man who guesses his color wrong will get his head chopped off, and the ones who guess correctly go free. Find a strategy that will minimize the number of wise men who die.
Source: Konstantin Knop and Alexander Shapovalov (Tournament of the Towns)