A logic problem by Andrew Droll
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?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The gnomes agree on the following strategy before the task starts:
The tallest (and therefore first-to-be-questioned) gnome will count the number of blue hats on the rest of the gnomes' heads. He can see every other gnome's hat, since he is the tallest. If this number is odd, he agrees to yell out "BLUE." If it is even, he agrees to yell out "RED."
Every gnome thus knows whether the total number of blue hats is even or odd. Moreover, every gnome remembers how many "BLUE" calls he has heard from taller gnomes as they have been questioned, and every gnome can see the hats on every shorter gnome's head, and can count these up.
So, on each gnome's turn, he takes the sum of the number of "BLUE" calls he has heard, ignoring the very tallest gnome's call completely, and adds this to the number of blue hats he sees on shorter gnomes' heads.
He now knows (a) whether the TOTAL number of blue hats is even or odd (based on the first dwarf's call), and (b) whether the total number of blue hats OTHER THAN HIS OWN (and the first dwarf's) is even or odd. This allows him to determine the color of his own hat with 100% certainty.
Sadly, the first (tallest) dwarf cannot do this. He is doomed to stay in servitude to the wizard, because the wizard can read minds and knows the gnomes' strategy. So based on the number of blue hats he materializes, the wizard already knows what color the first dwarf will call, and can make his hat the opposite color. However, the wizard cannot stop any of the other gnomes from going free.
So, exactly one gnome is left in service to the wizard at the end. :-)