[Guest]

seeing to popularity of the last one, here's version 2.

the prisoners are now arranged in a circular pattern, with each prisoner only able to see 7 out of 20 prisoners directly across from him. once again each prisoner has on a red hat or black hat, and they must find a strategy that saves the most.

[Guest]

I'll take a stab at saving half of the prisoners.

You could gaurantee the safety for at least half the prisoners. The first ten to go will have a 50/50 chance at surviving.

If you continue the diagram..Prisoner #1 sees prisoners 8-14..#2 sees 9-15...#3 sees 10-16....and so on.

Prisoner #1 calls out #11s hat color..#2 says #12s...#3 says #13s...all the way till prisoner #10 says #20s hat color. Now prisoners 11-20 know for certain what their hat colors are. That's if they must go in order starting with prisoner #1. Might be different if there is no order I'm not sure yet, I havn't looked at it very long.

[bushindo]

You can guarantee the safety of 13 prisoners, prisoner 1-7 each have 1/2 chance of dying. Here's a strategy

Prisoner 1-7 each look at the prisoners in his field of vision. Let black stand for +1, let red stand for -1. Say the color that correspond to the product of all the hats he sees. Example, red, red, black -> (-1)(-1)(+1) = 1 = black.

Lets consider the case of prisoner 8, he knows that prisoner 1 covers the following people

(P8, P9, P10, P11, P12, P13, P14)

while P2 covers the following set

( P9, P10, P11, P12, P13, P14, P15)

If P1 says the same color as P2, that implies P8 has the same color has prisoner 15. Otherwise, P8 has a different hat than P15. Since P8 can see P15, that makes it super easy for P8 to correctly says his color.

P8 up to P13 can apply this strategy. They will be saved for sure.

Now, lets consider player 14-20. Let's look at P14, he knows that player 1 sees the following set

(P8, P9, P10, P11, P12, P13, P14)

Since P8-P13 correctly said their color, and P1 already computed the product of the above set, it is trivial for P14 to compute his color. Continue this process until P20.

On average, this method can save 13 + 1/5 * 7 = 16.5 prisoners.

'

[Guest]

Hey Bushindo, I understand your method...

would that work for a plus 3? You know, if the first 5 had a red hat and then the next 2 had black. Then no matter what hat 15 was, prisoner 2 would still say the same colour. It would only plus or minus by one.

EDIT: wait... never mind. I think I get your method now....

only using the number for the first decision and then the colour changes depending on the colour of the next hat (regardless of positive or negative count)?

Edited June 22, 2009 by d31b0y