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.

umbrandsrtaoalexx_kaykgbooklogalexx_kayWant a level 1 hint?

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

alexx_kayHint #1: [

Spoiler (click to open)]Try solving for 2 prisoners and 2 colors.londoThis might be why I've always been bad at hat problems.

umbranalexx_kaytheycan work out ahead of time, that guarantees at least one prisoner survives."kgbooklogalexx_kaySpoiler (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.londoalexx_kaylondoumbranalexx_kaymetahackerAre they allowed to communicate then?

alexx_kaylaurionBut 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.

laurionEdited at 2013-01-10 12:10 am (UTC)alexx_kaykgbooklogOf 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."

herooftheageAnyway, 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)gyzkigyzkiMark Rafn [dagon.net]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.

alexx_kayhungrytigeralexx_kay