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?

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)

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.

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