Black Hat White Hat Death Game

Stump your fellow simians.
Polecat
Posts: 16
Joined: Thu Dec 02, 2004 6:49 pm
Location: Vancouver BC

Black Hat White Hat Death Game

Post by Polecat »

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 ?

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

Post by Marian »

What is the best strategy, and what is the MINIMUM number of PoWs you could save with it ?
Send in Chuck Norris!
[size=75]<b><u>Trolls that I'm not feeding</u></b>
Jarod3, Kilik, Interesting Ian

<b><u>Also on ignore...</u></b>
jj[/size]

[url=http://www.elementsgraphics.net/index.php?id=eggs][img]http://www.boomspeed.com/egraphics/o919a.gif[/img][/url]

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

Post by Beleth »

The best strategy I know of has only one POW having a 50% chance of dying, and all the rest live for sure. But I'll give people a chance to think about it before I post it.
"I can't tell if this is a love-fest or a pissing contest."
--MLynn

"Let's see some hugs... c'mon!"
--Quester_X

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

Post by Thumbo »

I can save all except the one at the back, who has only a 50/50 chance.
Last edited by Thumbo on Sat Mar 26, 2005 5:16 am, edited 1 time in total.

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

Post by Polecat »

Marian wrote:
What is the best strategy, and what is the MINIMUM number of PoWs you could save with it ?
Send in Chuck Norris!
I didn't say they were American PoWs. :P

User avatar
gnome
Posts: 23835
Joined: Tue Jun 29, 2004 12:40 am
Location: New Port Richey, FL

Re: Black Hat White Hat Death Game

Post by gnome »

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

But I can't think of how to achieve the results claimed in previous posts...

User avatar
Bearguin
Posts: 8093
Joined: Sun Jun 06, 2004 12:26 am
Title: Thankless Bastard!
Location: Get off my fucking lawn

Post by Bearguin »

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.

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

Re: Black Hat White Hat Death Game

Post by Polecat »

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 N-1.

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

Post by Beleth »

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.
"I can't tell if this is a love-fest or a pissing contest."
--MLynn

"Let's see some hugs... c'mon!"
--Quester_X

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

Post by Polecat »

Excellent solution.

Can you make this work with 3 hat colors (R, G, B) ?

Sentzeu
Posts: 102
Joined: Sat Aug 21, 2004 12:16 am

RGB

Post by Sentzeu »

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!

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

Post by Polecat »

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..M-1
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)

User avatar
specious_reasons
Posts: 6694
Joined: Mon Jun 07, 2004 7:58 pm

Re: Black Hat White Hat Death Game

Post by specious_reasons »

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 N-1.
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.

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 6-8 hex digits in my head that way.
ta-
DAVE!!!

User avatar
gnome
Posts: 23835
Joined: Tue Jun 29, 2004 12:40 am
Location: New Port Richey, FL

Re: Black Hat White Hat Death Game

Post by gnome »

Polecat wrote:but after the burying any talking (apart from your guess) means death for all.
I think according to the conditions of the question, responding in any way besides "black" or "white" means death for all.