July 10, 2007

What colour is your bandana?

Family

One night at camp when I joined the group at the fire, everyone in the family was discussing a riddle that only Boy in Black and With-a-Why knew how to solve. Boy in Black had learned it from his friend MathKid, who claimed that students at his college of Most Impressive Technology had made it up, although some of us suspect it's one of those brain teasers that's been around for a while and resurfaces in different forms.

Here's the riddle: An Evil Ruler has 100 gnomes. She lines them up in a straight line on a hill, so that each gnome can see all the gnomes ahead of him, but none of the gnomes behind him. She has 100 blue hats and 100 red hats. She puts a hat on each of the gnomes. A gnome cannot see his own hat -- or any of the hats behind him -- but he can see the hats of the gnomes ahead of him. He can hear what is happening behind him, but he cannot turn back and look.

Starting with the very last gnome in line, the Evil Ruler asks, "What colour is your hat?" The gnome is allowed to say one word, either "blue" or "red." If the prisoner answers correctly, he is allowed to live. If he says the wrong answer, he is killed. Then the Evil Ruler goes onto the next gnome.

The gnomes are given time to make a plan before this fun game begins. The Evil Ruler can hear them talking so it's not a secret plan. They cannot change any of the rules. Once the game begins, they cannot talk, except to answer the evil ruler. Each gnome must answer the Evil Ruler with one of two words, red or blue, and they may not signal anything with gestures or voice inflection.

Using logic, they come up with a plan that will save at least 99 of the 100 gnomes. What is the plan?


We all kept discussing this riddle at the fire, everyone talking at once and jumping in with ideas and arguing about the plan. Some family members got bored and went off to play cards or go to sleep, while others were obsessed with figuring out the answer. We quickly dropped the number of gnomes from 100 to ten, figuring that any plan that worked for ten would work for 100. I got playing cards, ten of them, some red and some black, and laid them on the bench to try to figure out the answer, a strategy which perhaps would have helped had it been light enough to see the cards.

Shaggy Hair Boy was the first to come up with an answer. He disappeared into the darkness with Boy in Black, and they returned to the fire, with Boy in Black saying, "Yep, he's got it," and Shaggy Hair smiling smugly. Naturally, he did not tell any of us the answer.

It wasn't until I'd left the campfire and was lying in the quiet darkness of the small tent I share with my husband that I came up with the answer to the riddle. I pushed my husband aside, threw off the old quilt we use as a blanket, put my clothes and sneakers back on, unzipped the tent, and went racing off across the field to the big tent where all the kids sleep so that I could make Boy in Black come out and hear my answer.

I returned to the tent, carefully zipping the nylon door behind me and tossing off the sneakers now wet from running across the dewy field. "I got it!" I exclaimed triumphantly to my husband.

"No, you aren't obsessive at all," he muttered.

The next day at breakfast, family members who hadn't been at the fire had to hear the riddle. You could tell which ones were determined to figure it out. They were the ones drawing little diagrams on paper plates, or staring at ten cards spread out on the ground, muttering under their breath. I could tell when Blonde Niece figured out the answer, just from the look on her face. Schoolteacher Niece jumped up and down when she got it.

Later that morning, we attempted to act out the riddle, using black and red bandanas put randomly on ten family members. With-a-Why posed as the Evil Ruler.

Riddle

The gnomes include my mother, my brother, my oldest sister, my youngest sister, three of my kids, and three of my nieces. Ignore the crazy gestures in the top photo. Hand signals are not allowed. The group kept breaking into the song YMCA, even though that was not part of the riddle at all.

90 comments:

RussianViolets said...

Since I'm the chronic English major and loathe logic, pray tell what the answer is. Inquiring minds want to know. :-)

Lorianne said...

You say the gnomes aren't allowed to use gestures or voice inflections...are they allowed to touch one another?

jo(e) said...

russianviolets: I was an English major, and I figured it out. Don't give up so easily.

Lorianne: No, they aren't allowed to touch each other.

seeker said...

I wouldn't want to be the last gnome in line.

skf said...

Jo(e),
Are they in line, but turned around, so the gnome at the bottom of the hill will be the only one who cannot see his hat?

skf

jo(e) said...

Nope. None of the gnomes can see his own hat (or bandana). Each gnome can see all the hats in front of him, but not his own, and none of the hats behind him.

It's not a trick question. There's a completely logical answer.

Nels said...

If you can hear what's behind you, can't you ask the gnome behind you, "hey, what color am I?" Then, all but the last could be saved.

Danny said...

I'll be thinking about this one all day. I'll run it by my 9 year-old son, he'll probably figure it out before me.

BTW, I love the campfire pictures. I just posted a campfire picture on my blog, but yours are better.

jo(e) said...

Nels: The gnomes are not allowed to talk once the game begins, except to say one word -- and the word has to be either red or black -- when the evil ruler asks the question.

jo(e) said...

(I'm not sure that the part about the gnomes was clear, so I went back and added a sentence to the original post.)

Danny: Yeah, kids always figure these things out faster than adults. They haven't let their brains atrophy like us old folks.

Oh, and to everyone: Seeker has already given a clue.

Lorianne said...

So, no gestures, intonations, or touching. Can an individual gnome cough, sneeze, or stomp her/his foot?

skf said...

Jo(e),
You can see I'm obsessed with this already.
Does each gnome call out the color of the hat in front of him, so the last one in line is the only one who might die?

jo(e) said...

Lorianne: No,no, and no. The only communication is the one word that each gnome says in response to the evil ruler's question. And that word must be red or black.

skf: That wouldn't work. If the gnome ahead of me has on a black bandana and I am wearing a red one, and I yell out "black," then I get killed.

Ampersand said...

The first one will know how many black and blue bandanas are in front of him, so he can figure out which one he is -- which ever color there is 99 of.

Then each one after him has to keep a count of how many before him of each color and how many in front of him.

The second guy knows which color was behind him and how many are in front of him. Which ever color total adds to 99 is the one that he/she is...

Am I close?

Busymomma66 said...

You are a cruel, cruel woman!!

I'm obsessed!!

landismom said...

I think I'm just going to have to come back for the answer to this one. It seems...unlikely...that I'm going to figure it out for myself.

I will, however, hit myself in the forehead as soon as I read the answer, I'm sure.

skf said...

This is just for fun, I know it's not right, but if I were a gnome, I'd have every one stick a mirror on their backs! If this were not allowed, I'd make every one stand in a circle so the Evil Ruler wouldn't know where to start!

Ampersand said...

That should say:

Then each one after him has to keep a count of how many called out before him of each color and how many he can see in front of him.

In my haste to give my answer, I did not take time to proofread.

Each gnome can see how many of each color is in front and keep a count of each color behind him from the verbal answers. If the gnome adds these two numbers up (as in, how many red in front of him and how many have called out red, and the same for black), one color total will equal 100 and one will equal 99. The one that equals 99 is the color bandana that he/she has.

jo(e) said...

Ampersand: You are on the right track. But remember, the evil ruler had 100 red hats and 100 blue hats, and she only used 100 hats altogether. So you can't use the color totals.

But you are right in saying that by time the evil ruler comes to a gnome, he can figure out eveyone else's hat color -- just not his own.

So that's the part that remains. How can each gnome figure out his own hat colour so that he can give the right answer and not be killed?

jo(e) said...

skf: Clever! But not allowed, of course. There is a logical answer to this. It's not a trick.

Lorianne said...

Ampersand, I'm confused by your answer. According to the directions, there are 200 bandanas: 100 black and 100 red. So keeping count won't work since you don't know the color makeup of the 100 un-used bandanas.

Since the Evil Ruler is starting at the back of the line, the last gnome is the only one who doesn't have someone behind her or him. So the last gnome has to guess blindly for a 50% chance of being killed.

What each subsequent gnome has to do is say "red" or "black" in such a way that a) indicates their own bandana color as indicated to them by the gnome immediately behind them and b) hints to the gnome immediately ahead of them what color their bandana is.

What I can't figure out, though, is how to give a "hint" to the gnome in front of you without using a gesture, intonation, or touch. If you could sneeze, cough, or stomp, you'd simply establish a code by which "red/cough" means "my bandana is red & so is yours" or "black/no cough" means "my bandana is black, but yours isn't."

But since Jo(e) says coughing isn't allowed, I can't figure out how to tell the gnome in front of me whether her/his bandana is the same color as mine. Can anyone think of a way around the prohibitions?

Ampersand said...

ahh, j(oe), I missed that critical piece of info...no wonder it seemed so easy, LOL.

*puts back on thinking cap*

Sean Burke said...

Lorianne, the problem with looking for a way around the prohibitions is that we've been explicitly told that there is no communication of any sort save for the response to the ruler.

For my part, I'm tempted to say that the first gnome gives a list of everyone else's colors in succession, but that both violates the rules (which we can't do) and goes against the ruling about communication. Plus, since the post says at least 99 gnomes are saved, probability is necessarily out. Quite a conundrum...

Emsy said...

Ahh... In the planning stage, the gnome in the back of the line tells the two people in front of him whether their hats are te same color or not. Every gnome in front of him does the same for the two people in front of him/her. Then, when the evil ruler comes along, the gnome at the back says the color of the hat in front of him...Everyone in front just remembers "same" or "different." Am I right?

I'm just sayin' said...

can they become a circle or shape other than straight line?

jo(e) said...

Emsy: Once the hats are on, the gnomes cannot talk. The only communication allowed once the hats are on is the one-word answer to the evil ruler.

They have to be in a straight line -- no circles.

Sean: The idea about the last gnome just yelling out all 99 colours in order is one of the solutions I came up with too, but it goes against the rules, so it's not the answer. Each gnome is allowed to say only one word -- red or blue.

Yes, there is a logical answer to the riddle. You are all getting closer to it.

Ampersand said...

Jo(e)!!

I'm pathetically obsessed...I even tried to google the riddle, but guess where google led me? Right to your blog, LOL. That made me feel guilty so I quickly closed the window before I could look at the other links :/.

I've thought about odd and even numbers, but that led to a dead end.

Good thing that our store has not been too busy today. And I sure do hope I can sleep tonight!

jo(e) said...

If anyone comes up with the answer (and you will know when you have it), send me an email so that you don't ruin it for anyone still trying to figure it out ....

Then I can announce in the comments which readers has figured it out, and that will drive everyone crazy.

S. said...

Jo(e), I don't have your email and the link won't work b/c of the way my browser's set up.

And no, I didn't have an aha moment yet, just a clarification question!

Scallen3, America Online

jo(e) said...

S: Oh, you could just ask a clarification question right here.

Anyhow, my email is writingasjoe@gmail.com

I'll try sending you an email ....

jo(e) said...

Now that I've read the deluge of emails from readers (and no one has the answer yet), let me clarify the rules once again: the gnomes cannot use voice inflection, pauses, gestures, movement, or anything to communicate to the other gnomes. The only method of communication, once the game starts, is the one-word answer to the evil ruler's question. And that answer must be either "red" or "blue."

It sounds impossible, I know, but really, there is a logical solution.

codfish said...

I've solved it, I've solved it!!! It took me about an hour - figured it out of obstinacy than anything else, really - jo(e), this is seriously obsessive!! It is evil too, cos I guess I should be spending the hour writing my thesis, but this was such awesome fun - thank you for posting this!!! :-D A wonderful, interesting post, as always. I'll e-mail you now!! (tho it's past midnight here, so I may not be very coherent......)

jo(e) said...

Tree of Knowledge just emailed me with the right answer -- although she says her husband gets the credit because he came up with it first.

And some of the other bloggers are getting really, really close ....

Busymomma66 said...

Will you give more hints to us thickheaded ones? Or the answer eventually?

I'm just not seeing it!!!

RussianViolets said...

You are cruel, jo(e). Please, oh please, e-mail my sick and pathetic ass the answer so I can stop obsessing and nurse my otherwise-illing head. :-) If you don't, I won't be able to sleep tonight, and it will be all your fault. hee

Me stoopid at logic, it seems.

RV (russianviolets@gmail.com)

jo(e) said...

Busymomma66: Here's my hint. If you read over all the comments here, and put all the information together, you should be able to come with the answer. Seriously.

Imagine that you are a gnome in the middle of the line. You know the hat colours of everyone ahead of you, and the hat colours of everyone behind you. What one piece of information could help you figure out what colour hat is on your own head?

jo(e) said...

Russianviolets: Oh, come on. You don't really want me to give you the answer. You are probably just minutes from figuring it out yourself.

RussianViolets said...

Oh, Gah! I'll keep stewing, then. All my solutions require more than one word. :-(

Madeleine said...

I have no idea what the answer is (yet) but I'm enjoying imagining the Monty Python version.

"Blue. No, Red. No, Blue."
"Off with her head!"

flutter said...

I don't suppose running away was an option?

Harriet Tubgnome said...

100 gnomes and one ruler. Liberation be ours! Down with Expedia.com! Free the gnomes from every lawn. We will not make boots for your amusement. We will no longer be called elves for Santa's sweatshops. We will rise above your silly games of riddles and RPG! For we our gnomes. And we'll bite your ankles off. Ni! Ni! Ni! Gnome Liberation begins now! Down with Game Theory! No more of Prisoners Dilemma! Now I must flee to Sequence a song on my resonator. I've got the David the gnome, hunted by trolls, reds gone blues.

Yankee T said...

oh dear lord-I take 18 days off the blog and I come back to a brain teaser. You're killin' me.
I'll give this to The Attorney to work on.

Jennifer said...

Ooh, that was fun. Must remember this one to torment my students with.

And it delights my sense of order that there are actually two possible solutions, although the gnomes had better be damn sure they all know which one they're using.

jo(e) said...

I woke up to all these emails filled with complicated formulas and theories ....

The answer can said in just a sentence or two.

Ampersand has figured it out, now, and so has Jodie.

Anonymous said...

Are you ever going to give the answer?

jo(e) said...

What? Give out the answer? But the fun of these kind of brainteasers is figuring it out for yourself.

It's not an impossible riddle. And there are all kinds of hints in the comments here.

jo(e) said...

Okay, in response to the latest batch of emails, let me just say that the plan will only work if all 100 of the gnomes understand it. So it has to be something that can be explained in just a few sentences. No complicated formulas.

With-a-Why understands it, and he just finished sixth grade.

jo(e) said...

Another blogger with the right answer! I just checked my email again, and Codfish has figured it out.

kathy a said...

please please please please please, post the answer!

codfish said...

Only after a couple of false alarms! Thanks again, jo(e), for the puzzle...... this really is a case of Keeping It Simple...! It was great fun, cheers again.

jo(e) said...

kathy a: Email me with what you've figured out so far, and I'll try to nudge you in the right direction.

Colleen said...

I don't know how steep that hill is, but everyone pictured is almost the same height! That's magic!

jo(e) said...

Colleen: I'm laughing because I was actually trying for the opposite effect. I told them to line up from tallest to shortest ... but I realized after taking the photo that I should have put the tallest at the top of the hill and the shortest at the bottom.

Boy in Black, at the head of the line, is about a foot taller than Drama Niece, at the end of the line.

jo(e) said...

Some of the email answers are getting really close.

Let me say again: The answer does not involve non-verbal communication. No stamping of feet, coughing or whistling, waving of arms, jumping or twirling. Those are against the rules. The only communication is through the one-word answer each gnome gives to the evil ruler.

KLee said...

Damn you, jo(e)! You've sucked me in again! First, the weffriddles, and now this. I have to devote some time to this one.....Argh.

Anonymous said...

No, honest. I will not feel cheated of an accomplishment if you post the answer. I could work on this from now until next Monday and I will not get it. It is not a failure of effort; it is a learning disability. So after a day or two so all the logic-puzzle people can have their fun, could you please let the rest of us who will never get it on our own steam know the answer?

-- bridgett

jo(e) said...

Klee: I have to admit that I was thinking yesterday, "I wonder when Klee is going to come over and get sucked into this ...."

Bridgett: Email me what you've figured out so far, and I will give you a nudge in the right direction.

Anonymous said...

If the first gnome guesses wrong, can the others hear it being killed?

jo(e) said...

Yes. Each gnome can hear everything going on behind him -- what words are said, and whether or not a gnome is killed.

jo(e) said...

In answer to the latest batch of emails ....

The gnomes may not move themselves around and put themselves in a pattern. They are in a straight line. The evil ruler is the one who puts the hats on. We don't know which hats she will use or whether or not she would choose a pattern.

The gnomes cannot whisper things in some other language or communicate with shrugs or nods or pauses or pokes or in anyway ....

Teri said...

do they steal half the hats first?

someone here at church said maybe the evil ruler is color blind?

this is driving me crazy.

jo(e) said...

Stealing the hats? But then she'd kill them all. She's evil, remember?

I like the idea of the evil ruler being color blind, but sadly, it's not really the answer to the riddle.

The real answer is simple logic. The riddle CAN be done. It's not a trick question.

kathy a said...

if there was a set number of hats of each color, then a math-type solution would work. but with 200 hats and 100 gnomes, the last gnome could see anywhere from 1-99 hats of the same color upstream -- and how could that count or its order be conveyed to the group with only one color word allowed to be communicated? [i am assuming here that the last gnome is the potential sacrificial gnome.]

once you left coughing out, another language as a signal was the extent of my brilliance. rouge and noir -- technically correct, no? no.

let's just face it, i am not the sharpest gnome in the garden.

September Blue said...

I've got it! After spending most of the day turning my brain inside-out over the thing, though. Keep trying, everyone...

Marie said...

This is really hurting me. I suck, suck, suck at logic problems. I had to practice like crazy for the logic part of the GRE. I'll never get it.

RussianViolets said...

Someone has to e-mail and tell me. I have been obsessing to no avail. I just cannot figure it out -- no matter how hard I try. Sad me.

So, who's going to put me out of my misery? And jo(e), you're a pistol! I cannot keep a secret for a millionth as long as you have.

zhoen said...

I prefer to read the end of a mystery first.

I shall just give up, this is not worth days of thought. I don't get it. You won't tell us. It's not fun for some of us.

Psycho Kitty said...

So you're saying that once the hats are placed on their head, none of the gnomes can change position or direction, nor touch the hats, nor make any verbal signal of any kind, neither through inflection, volume, etc?

jo(e) said...

Psycho Kitty: That's right. The communication is simply through the one-word answer that each gnome gives to the evil ruler.

Zhoen and Russian Violet: I don't want to put the answer in the comments while so many people are having fun trying to figure it out (Lots of people don't like being told the answer -- it ruins it for them.) I figure that anyone who really wants the solution can google it or email me behind the scenes.

For anyone who is looking for the answer through google, be sure to use hats rather than bandanas since the original riddle was about hats.

zhoen said...

Thanks for the hat googling pointer. Even reading the answer, I couldn't get it in my head, I'd never have figured it out. Good thing I'm not one of the gnomes, I'd have gotten all the rest killed.

Lorianne said...

I'm like zhoen. Knowing defeat when I see it, I googled the answer, and I still don't get it. Yeah, I understand the logic, but unless I had pen & paper, I'd never be able to keep track of how many hats there were of each color, so I'd be dead for sure. How could any gnome keep the colors (or numbers of colors) of 99 other gnomes in her or his head? I can barely remember my phone number... :-)

Jodie said...

If it is any consolation, this is the easy version of the riddle.

There is another version with three colors of hats.

Which raises the question: Can you solve it with any arbitrary number of hat colors? You can!

Anonymous said...

Funny...I just googled this and it came up on a Microsoft Interview question page.

-but there are just a bunch of guesses on this page, and none of them seems right to me (some aren't even comprehensible...).

Beth

Teri said...

google has saved me.
I think I get it.
Lorianne, i don't think you would have to keep track of all the other hat colors--just one.

Jennifer said...

Jodie,

Can you still save all but possibly one of the gnomes with 3 (or more) colors? I've got a solution for the 3 color version that will save all but possibly 2 gnomes. (And which would work to save all but 3 with 4 colors, etc). Is it possible to do better than that?

Still loving this riddle...

codfish said...

Jennifer,

I got the same conclusion as you (2 gnomes with 3 colours, 3 gnomes with 4 colours etc). I don't know if we can do better - the crux lies in the fact that we have to get to that one key value which makes all the deduction possible. To do that, we have to eliminate everything else so as to get that key value - therefore it will always be no. of colours minus one, the one being the gnome down the line who will finally have enough information to eliminate enough to deduce the key value.

Dunno if I'm making sense here, but I'm definitely still loving this riddle too! :-)

Jodie said...

Codfish and Jennifer,

Making perfect sense and I am pretty sure that is right. Something to do with degrees of freedom. But we would have to ask a real mathematician to be sure.

Jennifer said...

Jodie and codfish,

Actually, having thought about it some more, I think you can do better... I think you can save all but 2 gnomes with either 3 or 4 colors, all but 3 with 5, 6, 7, or 8 colors, and so on.

Though with more colors, explaining the plan to all the gnomes in line becomes a lot harder...

And rumor has it that I am a real mathematician. :-)

Sarah Sometimes said...

I just googled the answer--it's so breathtakingly simple once you see it, but I would never have gotten it. Crossword puzzles are more my speed! I think it's funny that the riddle is about gnomes, though--I can't remember the last time I had occasion to think about gnomes.

Anonymous said...

Can someone help me out? You know you're in a bad place when you can't even figure out what words/phrase to Google to figure out the answer! I can't do it! It's making me crazy! Augh! :)

thanks!

Norah

jo(e) said...

I haven't actually googled it (although all kinds of other people have so I know it's possible), but I can tell you the answer if you send me an email.

timna said...

I don't want the answer yet -- just read the question last night. But almond joy is gritting her teeth at swimming practice this morning.

Lorianne said...

Okay, this riddle is still bugging me (ack!) because even after googling the answer (yes, I'm a cheater), I still didn't "get" it. Yeah, I understand the logic...but as someone who has a short working memory, I wouldn't be able to remember/sort through what I'd heard about the hats in back of me and what I saw about the hats in front of me to figure out the hat on my own head.

("Working memory" is something Temple Grandin talks about in Animals in Translation: it's the ability to hold something like a math problem in your head while you calculate. Although I'm not autistic, like Grandin I can't remember numbers long enough to do a math problem in my head: the calculating takes too much brain-space for me to remember the numbers I'm working with, or the answer. I also can't spell out loud--I need to be able to write/see the letters on paper--and if you rattle off a phone number, I can't remember it long enough to write it down.)

Anyhow, given this mental glitch, I'd be screwed if I were a gnome in this line...unless the Evil Ruler let me have a pen & paper, which I doubt s/he'd allow!

But this morning, I had an insight: knowing I'd have a 50% chance of botching the simple formula for figuring out my own hat color, I'd volunteer to be the last gnome in line. The last gnome has no way of knowing her hat color, but she does do something very simple (and something involving very little working memory) to assure the other gnomes don't get killed. So since someone has to take a 50/50 gamble to save the other gnomes, I'd volunteer to be that gnome. Given the weird way my brain works, it's the only way to assure at least 99 gnomes survive the test.

With that, I'm done with this riddle. :-)

jo(e) said...

Lorianne: Are you sure you read the right answer? Because it's not a calculation -- it's just a matter of counting.

But hey, I love that you volunteered to be the last gnome. I am going to vote you "friend I'd most like to be taken prisoner with."

cloudscome said...

I am like Lorianne. I can't keep track of numbers in my head so I am sure I would lose it. I googled the answer and it still doesn't make sense to me. If the evil ruler randomly puts the hats on, how can it predictable?

cloudscome said...

Ha. As soon as I posted that I understood. Because there are only two colors. Sheesh I am slow.

kathy a. said...

will you please please please post an explanation? for the gnomes out here.

jo(e) said...

kathy a: You can see an explanation here .

Or anyone who wants can email me for a hint.

jo(e) said...

Forgot to say, for readers who aren't bloggers -- the word "here" in my last comment is a link. That's why it's blue. Click on it to find out the answer to the gnome riddle.

Jenevieve said...

Oh man, this took me forever to get! My brain must be seriously on holiday.