Previous Entry Share Next Entry
Colored Hat Puzzle
Bar Harbor
alexx_kay
From my friend Dorian:

Ten prisoners are told that, in a few minutes, they will be arranged in a circle, and a hat will be placed on each of their heads. There are ten possible hat colors: white, black, red, orange, yellow, green, blue, purple, brown and pink. The hat arrangement might be any mix of these, and no hat color is guaranteed to be represented at all. (So while there might be one of each color, there might also be 7 pink, 2 black and a green. Or 10 purples. Or 5 yellows and 5 whites. Etc. ) Each prisoner will see the hats of everyone else, but not his own hat.

Once in the circle, the prisoners will not be allowed to communicate with one another in any way, and after exactly one minute, they will all have to shout out a hat color *at the same time.* If a prisoner says the color of his own hat, he goes free. Otherwise, he's put to the sword.

The riddle is: find a strategy they can work out ahead of time, that guarantees at least one prisoner survives.

(The answer, just to let you know, is an actual math-y one, and not a figure-out-how-to-bend-the-rules solution.)

No spoilers in comments, please! If you think you know the answer, or want a hint (several levels available), please message me.
Tags:

  • 1
Hm. I'll be interested in the solution.

Clarification request: it appears that no information is transmitted between the prisoners in any way starting when they see the other prisoners in the circle, including hearing other prisoners announce their color choices. Is that correct?

Yes. If you like, you can rephrase it as they all write down their answers and they get simultaneously revealed.

I'm stumped. I can't see any way to do it without bending the rules, specifically "no guarantee any color is present", "absolutely no communication once hats are placed", and "simultaneous answers".

I guarantee that it is possible as stated.

Want a level 1 hint?

Sure. Maybe inside a spoiler tag, so others can see if they want.

I did think of a non-math-y solution: every prisoner says "The color of his own hat".

Haven't used a spoiler tag before, so here goes an attempt...

Hint #1: [Spoiler (click to open)]Try solving for 2 prisoners and 2 colors.

I am unable to convince myself that there is any arrangement in which someone can be given a N pieces of random information and come to a useful conclusion about piece N+1.

This might be why I've always been bad at hat problems.

I am also not yet convinced this one actually has a solution that guarantees a success, as stated.

Some*one* can't. That's why the puzzle is "find a strategy they can work out ahead of time, that guarantees at least one prisoner survives."

Still stumped. Usually these puzzles allow prisoners to either hear the other prisoners' answers or at least see who guesses first, before they make their own guess. But absolutely no communication and everyone guesses at the same time? No, not unless the prisoners can make faces or gestures during that minute (which wouldn't work for the photo version).

Hint #2: [Spoiler (click to open)]herooftheage's comment was deliberately misleading. The solution which guarantees "at least one" survivor in fact guarantees *exactly* one, no more, no less.

How can they be a collective when they can't transmit any information to each other?

They can communicate all they want *before* they see the hats, and can decide on a collective strategy to follow that doesn't require any communication *after* they see the hats.

I have spoiled myself on this puzzle and found the solution. It hurts my brain, but I think I am better off for it.

Actually, I have an answer. It is not a math-y one. Nor is it a "bending the rules" one. It is a linguistic-indeterminacy one.

I suspect that that *would* count as bending the rules, but feel free to run it by me :-)

Do the prisoners know the task ahead of time?

Are they allowed to communicate then?

Yes, and that's the major point of the puzzle. What strategy can they jointly arrive at that will save at least one?

Of course, it doesn't say they can't switch hats. Or take the hat off and look.

But that's rules lawyering and not actually interesting, so I'm going to presume the real solution works even if the prisoners are armless. Or bound hand and foot.

Oh, hey, here's a question: How restrictive is the communication barrier? Does the puzzle still work if they are simply shown pictures of the other nine people?

Edited at 2013-01-10 12:10 am (UTC)

Yes, the puzzle still works in that case. Arguably better, since it removes the temptation to try and weasel around "no communication".

Of course, it doesn't say they can't switch hats. Or take the hat off and look.

I'd say that's prohibited by "Each prisoner will see the hats of everyone else, but not his own hat."

I've actually done a ton of these hat puzzles, and so already know the answer to this one. (Actually, I had to work out the answer knowing the general sort of solution, but once you kind of know the domain of what's a right solution, that isn't so very hard.)

Anyway, there's a version of the problem which is either harder or easier, depending on your frame of mind: can you make a strategy where precisely one person gets the correct answer?

(Deleted comment)
I have a solution that seems almost too simple. It doesn't really bend the rules, and it could be described as math-based. But it's so simple, I must be missing something in the conditions.

—D'oh. Yes, too simple. But I'll keep thinking.

I have a too-simple solution as well - it occurred to me instantly, and I don't see how it fails.

It doesn't break or bend any rules, and it's not all that much math (maybe a bit of logic, and induction is needed to convince me that there's no way it doesn't work).

Is part of the problem description intentionally a red herring? My solution would work in a fairly wide range of scenarios that vary about how many of each other's hats are seen and when the declarations are made.


Send it along to me, and I'll tell you either that it's right, or how it fails.

Man, I know our prison system is overcrowded, but this seems like a really harsh way to solve it. Perhaps they should focus a bit more on rehabilitation and a bit less on hat-puzzles-of-doom.

Once I'm done with this thread, I intend to start another one about, "So, given that you're all prisoners of someone who is clearly an insane logician, *should* you follow the 'correct' strategy?"

  • 1
?

Log in

No account? Create an account