All Puzzles: Here
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: 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?
Great puzzle. First i didnt get it, but now it’s clear.
Maybe the answer would be clearer if you tell the reader that the smaller gnomes see either an odd or an even number of black caps and can “calculate” their own color.
Thanks! Have changed the wording of the puzzle and the solution to make them clearer.
Hi Gurmeet,
Do you have the solution for “Caps with 10 different colors”?
If you have it, can you please update the page with that?
Thanks,
Sai.
Bad solution: Save atleast n/10 people
Tallest person says the colour of the cap which maximum number of people are wearing. So, If the tallest says color c_1, all say c_1 and hence, atleast n/10 people are saved.
Better solution: Save a lot more than n/10 people ( But in the worst case n/10 people)
For n=100 say
Distribute them among sqrt(n) groups….
1, 11, 21, 31,…91
2, 12, 22, 32, …
and so on…
group i with people i + ksqrt(n) for all k
Last sqrt(n) people would sacrifice their lives and say the colour which is most common in their group.
So, in each sqrt(n) group, at least sqrt(n)/10 people would be saved and so, a total of n/10 would be saved.
Any better suggestions?
@Gurmeet: If you have the solution, Some hint please?
Hi Pratik, how about extending the parity idea to c colors — the first few gnomes could help all others by telling them the parities of various colors, as outlined below:
Assuming that colors can be ordered, the first c-1 gnomes announce the parity of the lowest c-1 colors among caps of 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. Thanks, Gurmeet
Nice solution…. Thanx a lot….
Keep posting such puzzles… :)
Better solution: (suggested by a friend)
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..
Ah, great! We could represent the (c-1)-digit binary number (whose bits represent the parities of the first c-1 colors) in base c. Then only the first ⌈ c * log 2 / log c ⌉ gnomes have to die.
How about the following solution:
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!