[Guest]

I saw how popular the Hats on Death Row was. So I thought I'd post a more difficult version. I browsed the topic and if I'm repeating this please let me know.

The conditions are exactly like the original puzzle. 20 prisoners will be assigned a random hat color they can't see. They will be lined up such that prisoner 20 sees all 19 hats in front of him, 19 sees all 18 in front of him and so on. Prisoner 20 goes first and can only call out a guess as to the color of his hat. And then 19 goes next. To add a humane twist, the warden will spare everyone's life if they use the optimal strategy to save as many lives as possible. There is one problem, there are 5 possible colors: Red, Blue, Black, Yellow and White.

What is the optimal strategy to maximize the number of prisoners who will call their correct hat color?

[Guest]

I saw how popular the Hats on Death Row was. So I thought I'd post a more difficult version. I browsed the topic and if I'm repeating this please let me know.

The conditions are exactly like the original puzzle. 20 prisoners will be assigned a random hat color they can't see. They will be lined up such that prisoner 20 sees all 19 hats in front of him, 19 sees all 18 in front of him and so on. Prisoner 20 goes first and can only call out a guess as to the color of his hat. And then 19 goes next. To add a humane twist, the warden will spare everyone's life if they use the optimal strategy to save as many lives as possible. There is one problem, there are 5 possible colors: Red, Blue, Black, Yellow and White.

What is the optimal strategy to maximize the number of prisoners who will call their correct hat color?

I'd think it would be similar to the stratagy for the original, or would we have to look at it in a whole nother way?

if the first person sees an even number of bs(blues and blacks) then they would say blue if they were both even, and black if they were both odd. if the bs were odd, and the lights(yellow and white) were even, then they'd say yellow if they were both even, and white if they were both odd. If both bs and lights were odd, then they say red.

Haven't tested it out to see how many would say the right color, but that's my first idea.

[Guest]

I'd think it would be similar to the stratagy for the original, or would we have to look at it in a whole nother way?

if the first person sees an even number of bs(blues and blacks) then they would say blue if they were both even, and black if they were both odd. if the bs were odd, and the lights(yellow and white) were even, then they'd say yellow if they were both even, and white if they were both odd. If both bs and lights were odd, then they say red.

Haven't tested it out to see how many would say the right color, but that's my first idea.

Yes, that would allow the next man to correctly gauge his color of hat, as only the changed parity would be the one which would be his color. Assuming that each man has correctly reasoned (and counted!), that should allow all the prisoners to correctly reason their color of hat.

Except the first man, of course. But that would be the optimal solution.

Edited June 30, 2009 by LighthouseGal

[bushindo]

I'd think it would be similar to the stratagy for the original, or would we have to look at it in a whole nother way?

if the first person sees an even number of bs(blues and blacks) then they would say blue if they were both even, and black if they were both odd. if the bs were odd, and the lights(yellow and white) were even, then they'd say yellow if they were both even, and white if they were both odd. If both bs and lights were odd, then they say red.

Haven't tested it out to see how many would say the right color, but that's my first idea.

But what about the Red hats?

Here's another method

Let (Red, Blue, Black, Yellow and White) correspond the the following values (0, 1,2,3, and 4). Let P1 add up all the hats he sees, divide the sum by 5, and announce the remainder.

For instance, suppose P1 sees 10 Red and 9 Blue, that would correspond to 10*0 + 9*1 = 9. 9 mod 5 is 4. P1 would then announce White during his turn.

P2 to P20 can then deduce their color using the same argument as in the original problem.

[Guest]

But what about the Red hats?

Here's another method

Let (Red, Blue, Black, Yellow and White) correspond the the following values (0, 1,2,3, and 4). Let P1 add up all the hats he sees, divide the sum by 5, and announce the remainder.

For instance, suppose P1 sees 10 Red and 9 Blue, that would correspond to 10*0 + 9*1 = 9. 9 mod 5 is 4. P1 would then announce White during his turn.

P2 to P20 can then deduce their color using the same argument as in the original problem.

Very well done. So, incredibly, it is possible to generalize the solution to accommodate any number of colors (even 1000's) and save at least 19 prisoners. Very cool in my book.