Imagine 100 gnomes with infallible abilities in logic and memory, no two of which are of the same height. These gnomes are subject to control by a super-intelligent all-powerful wizard who is up to no good.
The wizard gathers the gnomes, and describes the following trial that they will be forced to endure:
The gnomes will stand in a line in descending order of height. Each gnome will be able look down the line, and see the head of every shorter gnome, but will not be able to see the head of any of the taller gnomes (or be able to see his own head). The gnomes will not be able to communicate in any way during the task.
The wizard will then wave his wand, and materialize a hat on each gnome's head. Each hat will be either red or blue.
Then, the wizard will walk down the line, in descending order of height, and ask each gnome the color of his own hat. The gnome will declare his answer out loud for all to hear. If the gnome answers correctly, he will be allowed to go free. Otherwise, he will remain the wizard's subject.
The wizard allows the gnomes to talk in advance of this task to work out a strategy. You may assume that they are fully cooperative in this strategy (but remember, they have no way of communicating, besides when they announce their color to the wizard, during the task). The wizard can also read minds, so he will know the gnomes' strategy when the task starts (and may pick hat colors to ensure the worst outcome for the gnomes).
How many gnomes will still be subject to the wizard when the task is over?