An arbitrary number of PoWs are buried up to their necks in sand, all in a row, all facing the same way along the row (think of a crew boat).
Their captors give each of them a black or a white hat. PoWs can see the hats of ALL the PoWs in front, but not their own or the ones behind.
Starting at the "back", each PoW in turn has to guess his hat color. If he gets it right, he is saved. If he gets it wrong, he is shot. All other PoWs can hear his guess, and the resulting gunshot or lack thereof.
The PoWs were told the rules and allowed to develop a strategy before the burying, but after the burying any talking (apart from your guess) means death for all.
What is the best strategy, and what is the MINIMUM number of PoWs you could save with it ?
Black Hat White Hat Death Game

 Posts: 16
 Joined: Thu Dec 02, 2004 6:49 pm
 Location: Vancouver BC

 Posts: 2286
 Joined: Sun Jun 06, 2004 9:28 am
 Location: East of the Sun and West of the Moon

 Posts: 2868
 Joined: Tue Jun 08, 2004 8:55 pm
 Location: That Good Night

 Posts: 68
 Joined: Fri Jun 11, 2004 6:15 am

 Posts: 16
 Joined: Thu Dec 02, 2004 6:49 pm
 Location: Vancouver BC

 Posts: 25992
 Joined: Tue Jun 29, 2004 12:40 am
 Location: New Port Richey, FL
Re: Black Hat White Hat Death Game
So far I've thought of how to save approximately 75%... having each odd numbered POW call out the hat color of the guy in front of him, thus sparing that person and having a 50% chance of survival himself...Polecat wrote:An arbitrary number of PoWs are buried up to their necks in sand, all in a row, all facing the same way along the row (think of a crew boat).
Their captors give each of them a black or a white hat. PoWs can see the hats of ALL the PoWs in front, but not their own or the ones behind.
Starting at the "back", each PoW in turn has to guess his hat color. If he gets it right, he is saved. If he gets it wrong, he is shot. All other PoWs can hear his guess, and the resulting gunshot or lack thereof.
The PoWs were told the rules and allowed to develop a strategy before the burying, but after the burying any talking (apart from your guess) means death for all.
What is the best strategy, and what is the MINIMUM number of PoWs you could save with it ?
But I can't think of how to achieve the results claimed in previous posts...

 Posts: 8094
 Joined: Sun Jun 06, 2004 12:26 am
 Title: Thankless Bastard!
 Location: Get off my fucking lawn
Here's my thought.
First POW calls out the color of the hat ahead of him. Has a 50/50 chance but does let the next guy know the color of his hat. Lets say it's white.
Then, based on a prior agreed arrangment, the second guy looks at the guy ahead of him and sees a black hat. He knows his hat is white but needs to let the guy ahead of him now that he has a black hat. So instead of saying "white" he says "not black". He doesn't get shot and let the guy know ahead that his hat is black. Alternative, if he sees a white hat he will say white, not get shot and let the guy ahead know his hat is white.
I think that is within the rules.
First POW calls out the color of the hat ahead of him. Has a 50/50 chance but does let the next guy know the color of his hat. Lets say it's white.
Then, based on a prior agreed arrangment, the second guy looks at the guy ahead of him and sees a black hat. He knows his hat is white but needs to let the guy ahead of him now that he has a black hat. So instead of saying "white" he says "not black". He doesn't get shot and let the guy know ahead that his hat is black. Alternative, if he sees a white hat he will say white, not get shot and let the guy ahead know his hat is white.
I think that is within the rules.

 Posts: 16
 Joined: Thu Dec 02, 2004 6:49 pm
 Location: Vancouver BC
Re: Black Hat White Hat Death Game
BTW, I'm looking for the best "worst case" performance : assume the captors know about your strategy and do their best to confound it.
You can still save N1.
You can still save N1.

 Posts: 2868
 Joined: Tue Jun 08, 2004 8:55 pm
 Location: That Good Night
Okay, here goes.
The guy in back counts the number of black hats he sees.
If he sees an ODD number of black hats, he says "Black".
If he sees an EVEN number of black hats, he says "White".
The next guy knows the parity of the number of black hats the guy in back saw. If he sees the same parity of black hats (even or odd) then he knows his own hat is white. If he sees the other parity, he knows that his own hat is black.
You can go all the way up the line just by knowing whether the last guy saw an even or odd number of black hats, and listening to everyone previous.
The guy in back counts the number of black hats he sees.
If he sees an ODD number of black hats, he says "Black".
If he sees an EVEN number of black hats, he says "White".
The next guy knows the parity of the number of black hats the guy in back saw. If he sees the same parity of black hats (even or odd) then he knows his own hat is white. If he sees the other parity, he knows that his own hat is black.
You can go all the way up the line just by knowing whether the last guy saw an even or odd number of black hats, and listening to everyone previous.

 Posts: 16
 Joined: Thu Dec 02, 2004 6:49 pm
 Location: Vancouver BC

 Posts: 102
 Joined: Sat Aug 21, 2004 12:16 am
RGB
I'm not completely sure.
You can't make his solution work with three colors since it relies on the fact that he can give a unique answer based on the ODD/EVEN number of BLACK/WHITE hats, there is only two possibilities which matches the number of colors he has two chose from.
The problem is he can only pass on three different kinds of information and there are far more possible situations.
You would have to develop a strategy which sacrifices more than one!
Unless of course you can make guesses like "not green or blue" and "not blue or green" in that case it is possible two make a translation of the solution.
If RED=ODD, BLUE=ODD, GREEN=ODD then guess "RED"
If RED=ODD, BLUE=ODD, GREEN=EVEN then guess "BLUE"
If RED=ODD, BLUE=EVEN, GREEN=ODD then guess "GREEN"
If RED=ODD, BLUE=EVEN, GREEN=EVEN then guess "not blue or green"
If RED=EVEN, BLUE=ODD, GREEN=ODD then guess "not red or green"
If RED=EVEN, BLUE=ODD, GREEN=EVEN then guess "not red or blue"
If RED=EVEN, BLUE=EVEN, GREEN=ODD then guess "not green or blue"
If RED=EVEN, BLUE=EVEN, GREEN=EVEN then guess "not blue or red"
The first guy makes the guess and then the next guy checks to see if anything has changed from ODD to EVEN or vise versa.
It's much more complicated now.
Example: If the first guess is red, then the next guy knows that they are all odd from the former mans perspective, he then sees that green is even and therefore guesses green. Then the guy after him knows that all is odd except for green, if another color is even then his guess must be that color, if all is odd again then he chooses green.
They just pick after which of the colors switches from ODD to EVEN or EVEN to ODD.
But this is not an elegant solution, i.e if he is only allowed to guess "Green", "Red" and "Blue" then this solution would not work.
Again you would probably wind up sacrificing more than one!
You can't make his solution work with three colors since it relies on the fact that he can give a unique answer based on the ODD/EVEN number of BLACK/WHITE hats, there is only two possibilities which matches the number of colors he has two chose from.
The problem is he can only pass on three different kinds of information and there are far more possible situations.
You would have to develop a strategy which sacrifices more than one!
Unless of course you can make guesses like "not green or blue" and "not blue or green" in that case it is possible two make a translation of the solution.
If RED=ODD, BLUE=ODD, GREEN=ODD then guess "RED"
If RED=ODD, BLUE=ODD, GREEN=EVEN then guess "BLUE"
If RED=ODD, BLUE=EVEN, GREEN=ODD then guess "GREEN"
If RED=ODD, BLUE=EVEN, GREEN=EVEN then guess "not blue or green"
If RED=EVEN, BLUE=ODD, GREEN=ODD then guess "not red or green"
If RED=EVEN, BLUE=ODD, GREEN=EVEN then guess "not red or blue"
If RED=EVEN, BLUE=EVEN, GREEN=ODD then guess "not green or blue"
If RED=EVEN, BLUE=EVEN, GREEN=EVEN then guess "not blue or red"
The first guy makes the guess and then the next guy checks to see if anything has changed from ODD to EVEN or vise versa.
It's much more complicated now.
Example: If the first guess is red, then the next guy knows that they are all odd from the former mans perspective, he then sees that green is even and therefore guesses green. Then the guy after him knows that all is odd except for green, if another color is even then his guess must be that color, if all is odd again then he chooses green.
They just pick after which of the colors switches from ODD to EVEN or EVEN to ODD.
But this is not an elegant solution, i.e if he is only allowed to guess "Green", "Red" and "Blue" then this solution would not work.
Again you would probably wind up sacrificing more than one!

 Posts: 16
 Joined: Thu Dec 02, 2004 6:49 pm
 Location: Vancouver BC
For 3 colors odd/even parity (mod 2) is not enough. You need mod 3 parity. This will work for any number of colors.
[Note that (5)mod 3 = 1, not 2 or 2.]
For M colors:
Assign each color a number 0..M1
Each PoW calls ( 0  SUM(previous calls)  SUM(visible hats) ) mod M
Example : R=0, B=1, G=2
Sequence = G>R>G>G>R>B>R
1st guy sees 3R, 2G, 1B, so SUM of hats=5.
(0  0  5)mod 3 = 1, so he calls 1(Blue) (wrong)
Sum of calls = 1
2nd guy sees 2R, 2G, 1B, SUM of hats=5.
(0  1  5)mod 3 = 0, so he calls 0(Red)
Sum of calls = 1
3rd guy sees 2R, 1G, 1B, SUM of hats=3.
(0  1  3)mod 3 = 2, so he calls 2(Green)
Sum of calls = 3
4th guy sees 2R, 1B, SUM of hats=1.
(0  3  1)mod 3 = 2, so he calls 2(Green)
Sum of calls = 5
5th guy sees 1R, 1B, SUM of hats=1.
(0  5  1)mod 3 = 0, so he calls 0(Red)
Sum of calls = 5
6th guy sees 1R, SUM of hats=0.
(0  5  0)mod 3 = 1, so he calls 1(Blue)
Sum of calls = 6
7th guy sees nothing, SUM of hats=0.
(0  6  0)mod 3 = 0, so he calls 0(Red)
[Note that (5)mod 3 = 1, not 2 or 2.]
For M colors:
Assign each color a number 0..M1
Each PoW calls ( 0  SUM(previous calls)  SUM(visible hats) ) mod M
Example : R=0, B=1, G=2
Sequence = G>R>G>G>R>B>R
1st guy sees 3R, 2G, 1B, so SUM of hats=5.
(0  0  5)mod 3 = 1, so he calls 1(Blue) (wrong)
Sum of calls = 1
2nd guy sees 2R, 2G, 1B, SUM of hats=5.
(0  1  5)mod 3 = 0, so he calls 0(Red)
Sum of calls = 1
3rd guy sees 2R, 1G, 1B, SUM of hats=3.
(0  1  3)mod 3 = 2, so he calls 2(Green)
Sum of calls = 3
4th guy sees 2R, 1B, SUM of hats=1.
(0  3  1)mod 3 = 2, so he calls 2(Green)
Sum of calls = 5
5th guy sees 1R, 1B, SUM of hats=1.
(0  5  1)mod 3 = 0, so he calls 0(Red)
Sum of calls = 5
6th guy sees 1R, SUM of hats=0.
(0  5  0)mod 3 = 1, so he calls 1(Blue)
Sum of calls = 6
7th guy sees nothing, SUM of hats=0.
(0  6  0)mod 3 = 0, so he calls 0(Red)

 Posts: 6695
 Joined: Mon Jun 07, 2004 7:58 pm
Re: Black Hat White Hat Death Game
The last person, our poor sacrifice, yells out a number. The number converted to binary corresponds to the order of the prisoners and the hat in which they wear. 1 for white, 0 for black.Polecat wrote:BTW, I'm looking for the best "worst case" performance : assume the captors know about your strategy and do their best to confound it.
You can still save N1.
Although, I'd hate to be the prisoners, doing that calculation in your head would be killer, both figuratively and literally. Maybe the last prisoner yells out the number in hexadecimal, least significant digit first, to aid in the calculations. I could probably handle 68 hex digits in my head that way.

 Posts: 25992
 Joined: Tue Jun 29, 2004 12:40 am
 Location: New Port Richey, FL
Re: Black Hat White Hat Death Game
I think according to the conditions of the question, responding in any way besides "black" or "white" means death for all.Polecat wrote:but after the burying any talking (apart from your guess) means death for all.