First guy is a coin toss - let's wish him good luck.
His job is to establish the parity of black hats visible to him.
He says "Black" if he sees an odd number of black hats; "Red" otherwise.
By paying attention to what has been said, each prisoner will know his hat's color.
Example:
Second to speak hears "Black" and sees an even number of black hats.
He knows his hat is black [odd changed to even - must be his is black] and says "black".
Third guy has heard "black" and "black" and sees an even number of black hats.
He knows his hat is red [even stayed even - his hat can't be black] and says "red".
And so on, to the front of the line.
General algorithm:
The first time you hear "black", say to yourself "odd".
Each time your hear "black" after that, change the parity: "even", "odd", ... etc.
When it's your turn, if the black hats you see match the running parity, you're Red; Black otherwise.
Call out your color.
Subscribe to:
Post Comments (Atom)
4 comments:
You are assuming there are 10 black hats and 10 red hats. Since "the king is a ruthless man who likes to toy with his people's miseries", he could have any number of hats, such as 5 black and 15 red. So would your solution still work?
Mom
You're giving me a headache!
Yes, it does. It doesn't matter how many black and red there are, only that the number is even or odd, because if they know that information they can tell from what they see ahead of them what color their hat is. For example first guy says Red code word for odd. The rest of the people know there are an odd number of black hats. Guy number 19 sees 7 black hats in front of him, so he now knows that his hat is red. He says Red and lives. The next guy sees only 6 black hats in front of him so now he knows his hat is black. He says black and lives. Now all the others know that they are now looking for an even amount of black hats- so it goes on from there... Get it?
boo!
Post a Comment