Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Cap Colors

Puzzle

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 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

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

Solution

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?

Previous Puzzle: Four Ships

Four ships are sailing on a 2D planet. Each ships traverses a straight line at constant speed. No two ships are traveling parallel to each other. Their journeys started at some time in the distant past. Sometimes, a pair of ships collides. A ship continues its journey even after a collision. However, it is strong enough only to survive two collisions; it dies when it collides a third time. The situation is grim. Five of six possible collisions have already taken place (no collision involved more than 2 ships) and two ships are out of commission. What fate awaits the remaining two?

Next Puzzle: f(f(x)) = -x

Is it possible to write a function int f(int x) in C that satisfies f(f(x)) == -x? Without globals and static variables, of course.

12 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.