Gnome puzzle from MAKE 11, illustrated by Roy Doty
Here's an example of Roy Doty's work in MAKE. (Click on thumbnail for enlargement) (The puzzle was selected by Michael H. Pryor.)
LinkPoint of Gnome Return
One hundred very smart garden gnomes are snatched from their homes by an evil wizard. He tells them he is going to line them all up in a row, and place red and blue hats on each of their heads. They won't be able to see the color of their own hats or anyone's behind them, but they will be able to see the hats of the gnomes in front of them. The wizard will start at the back of the line and ask each gnome to tell the color of his own hat. Each gnome can only answer either "red" or "blue." If he gives the wrong answer, he will be led off to work on the wizard's landscaping for the rest of eternity. If he answers correctly, he will be returned to his own garden. Then the wizard will move on to the next gnome in line.
All of the gnomes will be able to hear the answers of the gnomes behind them, but they will not know if they were led off to forced labor or if they answered correctly and were set free. The gnomes are allowed to consult and agree on a strategy beforehand (while the wizard listens in) but after being lined up, they will not be able to communicate in any other way besides their answer of "red" or "blue" (in other words, they won't be able to change the pitch of their voice or give any other clues to the other gnomes once they are in line and the hats are placed on their heads). What strategy should the gnomes use to maximize the total number of gnomes that will be set free? Hint: They can do pretty well, even if the wizard hears their plan and puts the hats on in such a way to thwart whatever idea they come up with.
the latest
latest episodes
I told my brother this and his one line answer: Parity
I think I see the answer, but dont necessarily want to give it away-- HINT: one gnome has to sacrifice himself (or at least has a 50/50 chance of sacrificing himself) but all the others will escape the wizards toil).
Well, I guess I see the same answer as Anonymous from 1:54PM. You get a 50% chance of saving 99/100 gnomes, and a 50% chance of saving all 100. But the first gnome might be taking one for the team...alas.
#2: that plan only saves 1/2 the gnomes (worst case). Here is the plan that you propose
1. Last gnome says the color of the hat in front of it.
2. Next gnome can either say the color that the last gnome said, or the color of the hat in front of it.
So the plan would have to be:
1. If you are an even number of gnomes from the last (100th, 98th, etc.) you say the color of the gnome in front of you.
2. If you are an odd number of gnomes from the last, you say the color that the gnome behind you said.
This saves 1/2 the gnomes.
i must be missing something, because the answer seems way too obvious. each gnome just names the color of the hat for the gnome in front of them.
Answer this and you're ready for a job a Microsoft (this used to be a popular one amongst interviewers there)
Actually, given the fact that the evil wizard is listening in (and presuming that the goal of the EW is to kill gnomes), the first gnome is almost definitely a goner.
Parity isn't sufficient on its own. Recall that each answer needs to balance likeliness of correctness with ability to pass information forward. Each gnome could indicate a parity bit for all the hats he sees in front of him, but if that parity bit disagrees with the bit assigned to his color, then he'll get led away, and it's possible to line up the gnomes with their hats to force such a strategy to fail nearly completely.
In fact, any strategy that involves passing perfect information will necessarily be 99% defeatable. Starting from the front: assign the first gnome whichever hat you want. Then assign the next one the opposite color of the one that would indicate the information he wants to pass forward. And so forth. The one at the very front will be the only one to escape.
#5: If the wizard places them in alternate order, then they're all captured (except for the front one). Remember that the color information they're passing forward is also the guess they make.
if they all guess the same color, a solid 50% are guaranteed safe.
I remember hearing something like this, but I can't remember the answer.
Your can check the answer here:
http://makezine.com/images/11/gnome.html
Parity *is* sufficient on its own. Remember, "all of the gnomes will be able to hear the answers of the gnomes behind them."
p.s. if you find (and understand) the right solution, then you can generalize it to any number of hat colors (not just red and blue) as long as the set of possible colors is known in advance.
The first gnome just counts which hats are more numerous and says that color. Worst case: 50% saved; best: 100%.
All gnomes say the color of the hat in front of them. That will save all gnomes except for #1. Since the wizard is evil, he will intentionally make the hat of the gnome in front of the first gnome a different color than the first one's. The first gnome is toast unless the wizard is only "listening" as the problem states. If he can't see the gnomes they might be able to employ some gnomish sign language to indicate that the first gnome and only first gnome will say the opposite of the color in front of him. If the wizard does not see the trick, 100% might go free.
Love this puzzle, but I'm confused about the solution offered by post #12 (slight spoiler to that solution below):
What if the wizard hears your plan and makes all the hats blue? (Zero is an even number.) Then you lose 100% of your gnomes.
Or am I missing something there?
You're missing something.
Sadly, saying anything more is a giveaway.
#13: It can only be generalized to some extent. For n hat colors, I can't think of a way of doing it that wouldn't put in jeopardy n-1 gnomes. (With two hat colors, obviously, n-1 is 1, and you risk losing only one gnome.)
This is most obvious for the case of 100 hat colors. Clearly there's no way to pass forward sufficient information with the given method. The brute-force method of gnomes giving the hat colors of other gnomes actually does better in that case.
PARTIAL SPOILER ALERT
#16: Zero is an even number. So the first gnome is toast, but every remaining gnome knows that the number is even. Since each remaining gnome sees nothing but blue in front, and hears nothing but "blue" from behind (except for the special case of gnome 100), each gnome concludes that his hat must be blue - otherwise there would be only one red hat, and one is not an even number.
Generalized-
How many gnomes must die when there are n possible hat colors?
ok... we have a problem with the official answer
that seems clear.. 0 being an even number...
and the wizard knowing the gnomes' strategy means that all the gnomes are boned if the gnomes follow the strategy provided by the answer.
but... it still seems that the "odd red" strategy is best with the following twist:
gnome 100 must indicate if there are 0 red hats
(the gnomes must agree that his answer regardless of whether it is coded as red or blue only indicates if there are NO other coloured hats)
then gnome 99 is faced with a problem.. there are an even number of gnomes in front of him.. 98
therefore the strategy proposed does not work yet.
it is only gnome number 98.. with 97 gnomes in front who can begin the strategy successfully.
(I still think the strategy proposed by the official answer is the best one if you eliminate the "no hats" possibility)
(but 97 seems to be the most gnomes guaranteed to be free)
i prefer the gnomes creating a system whereby they
give a binary description of all the remaining gnomes' hats.. if (big if.. because i cant do stats) there are 10 000 possible combinations of gnomes hats then only 15 gnomes are needed to describe the 10 000 possible combinations of gnome hats. or 16 gnomes to describe 20 000 possible combinations.. blah someone please criticize this answer because it seems ridiculous.
thanks
PARTIAL SPOILER ALERT
#18: Think modulo
You're making puzzles about gnome slaves?!
Too soon.
Guys, lighten up. The gnomes are not dying, they're only being enslaved.
It seems there is a definite chance of saving 50% of the gnomes from enslavement, and a 50% chance that the OTHER 50% will be saved (in other words statistically an average of 75% would be saved). The first gnome says the color of the hat in front of him, it MAY be his hat color too, so he has a 50% chance of escaping, but the gnome in front of him knows his own hat color now, and can escape, the next gnome repeats the process with his own 50% chance, and the gnome after him again has 100% chance. For this to work, the gnomes have to keep track as the wizard goes down the line.
#25 - The wizard can hears their planning and can capture all 100 gnomes by simply alternating their hat colors, with that solution.
The official answer in #12 really is the best you're going to do (and pretty damn good at that), I don't understand the problem with it that #21 thinks is so clear...
#26-- No, you are incorrect, no matter how the wizard arranges the gnomes, AT LEAST half will escape-- even if he alternates red/blue, for example, a red-hat gnome would say "blue", naming the hat in front of him, thus that next gnome would know his hat was blue and escape, and so on up the line (essentially, if they were arranged red/blue/red/blue/etc, they would all say the same color, and half would escape.
the fact that the wizard can hear their plans and act accordingly does erase the other 25 I predicted might escape though.
#26: I agree with you. We have real-world computer hardware that uses this principle at all times, and it seems to have worked fine for decades.
The problem seems to come from someone misunderstanding the solution (something about how the fact that "0 is an even number" makes the solution incomplete, which is a mistake).
A group of us got into this puzzle over beers yesterday.
(requisite spoiler alerts)
My take is that the solution is seriously flawed because it requires at least one hat of each color. It doesn't allow for a zero amount for either. And since you have a wizard that will create a red or blue zero amount based on your strategy, that makes it not work at all.
Re-read the solution behind the link in #12: The gnomes agreed that if they saw an even number of red hats in front of them, they would say "red." That means if there were zero red hats (zero is an even number), they would all say "red," even though they were all wearing blue hats.
The comments dismissing this issue incorrectly state that the gnomes agreed to say "blue" if they saw an even number of red hats. But even if they had, the wizard could still trip them up there with all red hats. Then every other gnome would see an even number of red hats in front of him and incorrectly guess his hat was blue. On the upside, the first gnome would actually be safe.
A group of us got into this puzzle over beers yesterday.
(Requisite spoiler alerts...)
The solution in #12 is clever but flawed because it requires at least one hat of each color. Zero hats of either color = a problem. And since you have a wizard that will create a red or blue zero amount based on your strategy, that makes it not work.
Re-read the solution behind the link in #12: The gnomes agreed that if they saw an even number of red hats in front of them, they would say "red" (not "blue"). That means if there were zero red hats, an even number, they would all have to say "red," even though they were all wearing blue hats. They might realize their answer of "red" didn't make sense with all the previous gnomes also saying "red," but if they changed their answer to "blue" arbitrarily, they'd throw off half the gnomes after that.
Zero is an even number by definition, but the point is that it doesn't matter whether it's defined as odd or even, just that it can't be both. And whichever one you choose, the wizard can trip you up with it.
The comments dismissing this issue incorrectly state that the gnomes agreed to say "blue" if they saw an even number of red hats. But even if they had agreed to do that, the wizard could just give them all red hats. Then every other gnome would see an even number of red hats in front of him and incorrectly guess his hat was the only remaining blue one.
SPOILER ALERT
(I'm going to basically spell this out now, so people who still want to figure this out on their own should skip this comment)
People who think there is a flaw in the parity strategy don't understand the strategy. It always saves N-1 of the gnomes, even if all the hat colors are the same.
The point that you are probably missing is that ONLY the first gnome to speak gives parity.
The second gnome to speak uses the parity bit, and all the colors in front of him, to deduce his own hat color.
The third gnome has heard the parity bit. She also knows the second gnome has answered correctly! She can use this information, plus the colors she sees in front of her, to deduce her own hat color.
Now iterate. Each gnome knows (a) the parity bit (b) all the hat colors s/he can't see (because they have heard all the answers) and (c) all the hat colors in front of them (because they can see them). This is sufficient for any gnome to deduce his/her own hat color.
As I said in #13, this is generalizable to more than two colors of hats. (In answer to the objection in #18, see the response someone else gave in #22.)
Actually, the gnomes don't know if the others were correct or incorrect:
"but they will not know if they were led off to forced labor or if they answered correctly and were set free."
That's a key aspect.
#31: Thanks, that was the missing piece for me (that only the first gnome uses parity, not all of them).
@ #32: I mean "know" in the sense that the gnomes presumably can trust each other to be able to count and come up with the correct answer. (Remember, the problem stipulates "very smart" gnomes.)
@#31: (citing #22 as an answer to the objection in #18)
I still don't see how there is any way to pass sufficient information for the solution to be generalized completely. Even with modulo arithmetic, you can only pass information on one hat color at a time, I think. So you still lose n-1 gnomes for n hat colors.
(Just to make this clear: this assumes that one understands that the solution to the basic problem as stated does, indeed, work as stated and save 99 gnomes.)