[bushindo]

Suppose you and 11 friends are invited to play a game. The game is as follows:

1) All of the 12 participants are blinded folded and have either a red or blue hat placed on each of their heads.

2) The host then randomly arrange them in a circle in such a way that each participant can only see the 4 neighbors immediately to his/her left and the 4 neighbors immediately to his/her right.

3) The blindfolds are removed, and each participant can look at the hat of his 4*2 = 8 immediate neighbors.

4) Each person must then write down a guess for his/her hat. Each guess must either be 'red' or 'blue', and must be written at the same time.

5) The game host then looks at all the guesses. If they are ALL correct, the 12 participants win. If 1 or more guesses are incorrect, the participants lose.

Please assume that the players do not cheat. Any attempt to exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc. will lead to an automatic loss. If everybody randomly guess their hat, then the chance of winning the game is 1/2¹² = 1/4096. Fortunately, there are better strategies than that.

The players can discuss a strategy before playing the game. Determine a strategy that has a winning rate equal to or greater than 3/64 (that's 192 times better than random guessing).

Edited December 15, 2010 by bushindo

[Guest]

The hats are random. Each person, will have to guess which hat is on their own head. The 8 people the person can see have no effect on what is on their own head. They may all have blue hats, but if it is random, your hat is still 50/50 its blue.

[bonanova]

There is a way for pairs of players to guess that guarantees exactly one is right and the other is wrong.

I'll try to see whether simply avoiding that scenario on a pairwise basis [i.e. both right or both wrong]

increases the overall chances enough.

I suspect it won't be enough.

[Guest]

I agree - the question is how many hats of each color there are... if that is unknown, anyone else's hat color should be pointless.

The hats are random. Each person, will have to guess which hat is on their own head. The 8 people the person can see have no effect on what is on their own head. They may all have blue hats, but if it is random, your hat is still 50/50 its blue.

[araver]

Cheesner and IdoJava, while it is perfectly OK to share your opinions in the thread if you think the puzzle is broken/flawed somehow, it is not OK to vote down on a puzzle or a post unless you are absolutely sure that the puzzle is not solvable/wrong. Voting a puzzle should follow the Thank you.

As a hint, you might want to try this puzzle first:

.

[Guest]

1. If you see everyone else has the same color hat, guess that color. If all players use this strategy they will win 2/4096 times - when all plalyers have all red or all blue hats.

2. If there is an alternating patern in front and behind, guess the opposite color of the person sitting next to you. This gives the group another 2/4096 chance of winning.

3. If there are alternating doubles on both sides of you (RRBB®RBBR) choose the corresponding color to complete the pattern. There's another 2/4096.

4. Again for alternating triples (RRRB(B)BRRR) and get another 2/4096.

5. Quad - (RRRR(B)BBBR) - another 2/4096

6. (RRRR®BBBB)

7. (RRRR®RBBB)

8. (RRRB(B)BBBB)

9. (RRBR®BRRB)

10. (RRRB®RRBR)

Finally, if none of these patterns exist everyone will guess a random color and have 1/4096 of being right.

This gives 21/4096 chance of being right. Still far short but 21 times better than random guessing.

Maybe there are more patterns I'm not thinking of or maybe this isn't the right strategy at all.

[araver]

Not a strategy, just an observation:

I just figured out that the space of symmetrical deterministic strategies (i.e. where all players use the same deterministic function for their answer) is around 2^256. Which discourages any attempt to exhaustively search for an optimal strategy.

Bushindo - is that why you did not ask for an optimal strategy this time?

[bushindo]

Not a strategy, just an observation:

I just figured out that the space of symmetrical deterministic strategies (i.e. where all players use the same deterministic function for their answer) is around 2^256. Which discourages any attempt to exhaustively search for an optimal strategy.

Bushindo - is that why you did not ask for an optimal strategy this time?

Yes, I did not ask for the optimal strategy on purpose. You're very sharp. This puzzle is more like an ah-ha type of puzzle. It does not, and should not, require excessive charting or computing.

EDIT: I apologize for the double post. Something seems to be wrong with my browser.

Edited December 16, 2010 by bushindo

[bushindo]

Not a strategy, just an observation:

I just figured out that the space of symmetrical deterministic strategies (i.e. where all players use the same deterministic function for their answer) is around 2^256. Which discourages any attempt to exhaustively search for an optimal strategy.

Bushindo - is that why you did not ask for an optimal strategy this time?

Yes, I did not ask for the optimal strategy on purpose. You're very sharp. This puzzle is more like an ah-ha type of puzzle. It does not, and should not, require excessive charting or computing.

[superprismatic]

Suppose you and 11 friends are invited to play a game. The game is as follows:

1) All of the 12 participants are blinded folded and have either a red or blue hat placed on each of their heads.

2) The host then randomly arrange them in a circle in such a way that each participant can only see the 4 neighbors immediately to his/her left and the 4 neighbors immediately to his/her right.

3) The blindfolds are removed, and each participant can look at the hat of his 4*2 = 8 immediate neighbors.

4) Each person must then write down a guess for his/her hat. Each guess must either be 'red' or 'blue', and must be written at the same time.

5) The game host then looks at all the guesses. If they are ALL correct, the 12 participants win. If 1 or more guesses are incorrect, the participants lose.

Please assume that the players do not cheat. Any attempt to exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc. will lead to an automatic loss. If everybody randomly guess their hat, then the chance of winning the game is 1/2¹² = 1/4096. Fortunately, there are better strategies than that.

The players can discuss a strategy before playing the game. Determine a strategy that has a winning rate equal to or greater than 3/64 (that's 192 times better than random guessing).

The following function, taking the 4 before concatinated with the 4 after to a guess,

has a winning probability of 9/128 (or 288 times random guessing):

00000000 0

00000001 1

00000010 1

00000011 1

00000100 0

00000101 0

00000110 1

00000111 0

00001000 1

00001001 1

00001010 1

00001011 1

00001100 0

00001101 1

00001110 1

00001111 0

00010000 1

00010001 1

00010010 1

00010011 1

00010100 0

00010101 0

00010110 1

00010111 1

00011000 0

00011001 0

00011010 1

00011011 0

00011100 1

00011101 1

00011110 0

00011111 0

00100000 1

00100001 1

00100010 1

00100011 0

00100100 1

00100101 0

00100110 0

00100111 1

00101000 0

00101001 0

00101010 0

00101011 0

00101100 0

00101101 1

00101110 1

00101111 0

00110000 0

00110001 0

00110010 0

00110011 0

00110100 0

00110101 1

00110110 1

00110111 0

00111000 1

00111001 1

00111010 1

00111011 1

00111100 0

00111101 0

00111110 0

00111111 1

01000000 1

01000001 1

01000010 1

01000011 1

01000100 0

01000101 1

01000110 0

01000111 1

01001000 1

01001001 1

01001010 0

01001011 0

01001100 0

01001101 0

01001110 0

01001111 0

01010000 1

01010001 0

01010010 0

01010011 0

01010100 0

01010101 1

01010110 1

01010111 1

01011000 0

01011001 1

01011010 1

01011011 0

01011100 1

01011101 1

01011110 0

01011111 1

01100000 1

01100001 0

01100010 0

01100011 0

01100100 0

01100101 0

01100110 0

01100111 1

01101000 0

01101001 0

01101010 1

01101011 1

01101100 1

01101101 0

01101110 1

01101111 0

01110000 1

01110001 1

01110010 1

01110011 1

01110100 0

01110101 1

01110110 0

01110111 0

01111000 0

01111001 0

01111010 0

01111011 0

01111100 0

01111101 1

01111110 0

01111111 1

10000000 1

10000001 0

10000010 1

10000011 1

10000100 1

10000101 1

10000110 0

10000111 1

10001000 1

10001001 0

10001010 1

10001011 1

10001100 0

10001101 1

10001110 0

10001111 0

10010000 1

10010001 0

10010010 0

10010011 0

10010100 0

10010101 0

10010110 0

10010111 0

10011000 0

10011001 1

10011010 0

10011011 0

10011100 1

10011101 1

10011110 0

10011111 1

10100000 1

10100001 1

10100010 0

10100011 0

10100100 1

10100101 0

10100110 1

10100111 0

10101000 1

10101001 0

10101010 1

10101011 1

10101100 1

10101101 1

10101110 1

10101111 1

10110000 0

10110001 0

10110010 1

10110011 1

10110100 1

10110101 1

10110110 1

10110111 1

10111000 1

10111001 1

10111010 1

10111011 0

10111100 1

10111101 0

10111110 1

10111111 1

11000000 1

11000001 1

11000010 1

11000011 0

11000100 0

11000101 1

11000110 0

11000111 0

11001000 1

11001001 0

11001010 0

11001011 1

11001100 0

11001101 1

11001110 1

11001111 1

11010000 1

11010001 1

11010010 0

11010011 1

11010100 0

11010101 0

11010110 1

11010111 0

11011000 0

11011001 1

11011010 0

11011011 1

11011100 0

11011101 0

11011110 0

11011111 0

11100000 0

11100001 1

11100010 1

11100011 0

11100100 1

11100101 1

11100110 1

11100111 1

11101000 0

11101001 0

11101010 1

11101011 0

11101100 0

11101101 1

11101110 0

11101111 0

11110000 1

11110001 0

11110010 0

11110011 1

11110100 0

11110101 1

11110110 0

11110111 0

11111000 0

11111001 1

11111010 1

11111011 0

11111100 1

11111101 1

11111110 1

11111111 1

[bushindo]

The following function, taking the 4 before concatinated with the 4 after to a guess,

has a winning probability of 9/128 (or 288 times random guessing):

00000000 0

00000001 1

00000010 1

00000011 1

00000100 0

00000101 0

00000110 1

00000111 0

00001000 1

00001001 1

00001010 1

00001011 1

00001100 0

00001101 1

00001110 1

00001111 0

00010000 1

00010001 1

00010010 1

00010011 1

00010100 0

00010101 0

00010110 1

00010111 1

00011000 0

00011001 0

00011010 1

00011011 0

00011100 1

00011101 1

00011110 0

00011111 0

00100000 1

00100001 1

00100010 1

00100011 0

00100100 1

00100101 0

00100110 0

00100111 1

00101000 0

00101001 0

00101010 0

00101011 0

00101100 0

00101101 1

00101110 1

00101111 0

00110000 0

00110001 0

00110010 0

00110011 0

00110100 0

00110101 1

00110110 1

00110111 0

00111000 1

00111001 1

00111010 1

00111011 1

00111100 0

00111101 0

00111110 0

00111111 1

01000000 1

01000001 1

01000010 1

01000011 1

01000100 0

01000101 1

01000110 0

01000111 1

01001000 1

01001001 1

01001010 0

01001011 0

01001100 0

01001101 0

01001110 0

01001111 0

01010000 1

01010001 0

01010010 0

01010011 0

01010100 0

01010101 1

01010110 1

01010111 1

01011000 0

01011001 1

01011010 1

01011011 0

01011100 1

01011101 1

01011110 0

01011111 1

01100000 1

01100001 0

01100010 0

01100011 0

01100100 0

01100101 0

01100110 0

01100111 1

01101000 0

01101001 0

01101010 1

01101011 1

01101100 1

01101101 0

01101110 1

01101111 0

01110000 1

01110001 1

01110010 1

01110011 1

01110100 0

01110101 1

01110110 0

01110111 0

01111000 0

01111001 0

01111010 0

01111011 0

01111100 0

01111101 1

01111110 0

01111111 1

10000000 1

10000001 0

10000010 1

10000011 1

10000100 1

10000101 1

10000110 0

10000111 1

10001000 1

10001001 0

10001010 1

10001011 1

10001100 0

10001101 1

10001110 0

10001111 0

10010000 1

10010001 0

10010010 0

10010011 0

10010100 0

10010101 0

10010110 0

10010111 0

10011000 0

10011001 1

10011010 0

10011011 0

10011100 1

10011101 1

10011110 0

10011111 1

10100000 1

10100001 1

10100010 0

10100011 0

10100100 1

10100101 0

10100110 1

10100111 0

10101000 1

10101001 0

10101010 1

10101011 1

10101100 1

10101101 1

10101110 1

10101111 1

10110000 0

10110001 0

10110010 1

10110011 1

10110100 1

10110101 1

10110110 1

10110111 1

10111000 1

10111001 1

10111010 1

10111011 0

10111100 1

10111101 0

10111110 1

10111111 1

11000000 1

11000001 1

11000010 1

11000011 0

11000100 0

11000101 1

11000110 0

11000111 0

11001000 1

11001001 0

11001010 0

11001011 1

11001100 0

11001101 1

11001110 1

11001111 1

11010000 1

11010001 1

11010010 0

11010011 1

11010100 0

11010101 0

11010110 1

11010111 0

11011000 0

11011001 1

11011010 0

11011011 1

11011100 0

11011101 0

11011110 0

11011111 0

11100000 0

11100001 1

11100010 1

11100011 0

11100100 1

11100101 1

11100110 1

11100111 1

11101000 0

11101001 0

11101010 1

11101011 0

11101100 0

11101101 1

11101110 0

11101111 0

11110000 1

11110001 0

11110010 0

11110011 1

11110100 0

11110101 1

11110110 0

11110111 0

11111000 0

11111001 1

11111010 1

11111011 0

11111100 1

11111101 1

11111110 1

11111111 1

This is excellent. The strategy above is more optimal than mine, which can only win 1/16 times (256 times that of random guessing). Good work.

Let's first consider the simple case where 3 people stand in a circle. Each can see the other two, and they need to all correctly guess their own hat color. One strategy is for them to assume that there are an even number of red hats among all three of them. Each person can then compute their hat color from what he sees, and the chance of their winning the game is 1/2 (this is because the total number of red hats should be equally likely odd or even).

In the graph above, the circle represents the positions of these participants. Notice that each person in a circle of a particular color can see the remaining two people of the same color. For instance, person number 1 can see 5 and 9, person 5 can see 1 and 9, and person 9 can see 5 and 1. This is a solved situation, so the puzzle with 12 people can be reduced to four 3-people games. From here, we can formulate the following strategy,

1) Each person looks at the two people at the edge of his vision. For instance, person 1 would look at person 5 and 9.

2) Each person then assumes that there are an even number of red hats among the two people in step 1 and himself.

3) Each person then derive his hat color from this.

The chance of winning is (1/2)⁴ = 1/16. This method, however, is not optimal, as superprismatic has shown in this solution.

Edited December 16, 2010 by bushindo

[Guest]

This is excellent. The strategy above is more optimal than mine, which can only win 1/16 times (256 times that of random guessing). Good work.

Let's first consider the simple case where 3 people stand in a circle. Each can see the other two, and they need to all correctly guess their own hat color. One strategy is for them to assume that there are an even number of red hats among all three of them. Each person can then compute their hat color from what he sees, and the chance of their winning the game is 1/2 (this is because the total number of red hats should be equally likely odd or even).

In the graph above, the circle represents the positions of these participants. Notice that each person in a circle of a particular color can see the remaining two people of the same color. For instance, person number 1 can see 5 and 9, person 5 can see 1 and 9, and person 9 can see 5 and 1. This is a solved situation, so the puzzle with 12 people can be reduced to four 3-people games. From here, we can formulate the following strategy,

1) Each person looks at the two people at the edge of his vision. For instance, person 1 would look at person 5 and 9.

2) Each person then assumes that there are an even number of red hats among the two people in step 1 and himself.

3) Each person then derive his hat color from this.

The chance of winning is (1/2)⁴ = 1/16. This method, however, is not optimal, as superprismatic has shown in this solution.

Both of these strategies are pointless. In no way in the problem is there a dependence of one person's hat upon the other.

superprismatic listed all the permutations of a 8 digit binary number and got 256 combinations. The ninth digit (your hat) still has an equal chance of being a '1' or a '0'.

If you wanted you could list all the permutations of a 11 digit binary number, and get 2048 combinations. The 12th person, your guess, can still be either 1 or 2 with equal probability. Or 1 in 4096 - the odds of everyone guessing correctly.

Edited December 17, 2010 by Cheesner

[superprismatic]

Both of these strategies are pointless. In no way in the problem is there a dependence of one person's hat upon the other.

superprismatic listed all the permutations of a 8 digit binary number and got 256 combinations. The ninth digit (your hat) still has an equal chance of being a '1' or a '0'.

If you wanted you could list all the permutations of a 11 digit binary number, and get 2048 combinations. The 12th person, your guess, can still be either 1 or 2 with equal probability. Or 1 in 4096 - the odds of everyone guessing correctly.

It's much easier to use bushindo's excellent example to explain.

Let's look at positions 1, 5, and 9 in his diagram. What he is

saying is that, if there are an even number of red hats on these

guys (which he wants them to assume), then each of them will

correctly deduce his hat color. But, if the assumption about

them having an even number of red hats amongst them is incorrect,

then they will all be wrong (not just one or two, but all three

of them will be wrong). So, under bushindo's scenario, he is

dividing all the possible hat assignments into 2 camps (odd

number of red hats, and even number of red hats). Since the

probability that the three have an even number of red hats is

1/2, this means that all three can correctly announce their hat

colors with probability 1/2. I hope this explains the apparent

paradox.

[Guest]

It's much easier to use bushindo's excellent example to explain.

Let's look at positions 1, 5, and 9 in his diagram. What he is

saying is that, if there are an even number of red hats on these

guys (which he wants them to assume), then each of them will

correctly deduce his hat color. But, if the assumption about

them having an even number of red hats amongst them is incorrect,

then they will all be wrong (not just one or two, but all three

of them will be wrong). So, under bushindo's scenario, he is

dividing all the possible hat assignments into 2 camps (odd

number of red hats, and even number of red hats). Since the

probability that the three have an even number of red hats is

1/2, this means that all three can correctly announce their hat

colors with probability 1/2. I hope this explains the apparent

paradox.

ooooohhh. I think I see what you're saying. Thanks!

[araver]

Kudos superprismatic : you managed to find perhaps the optimal strategy, where I would have expected search algorithms would have failed.

Bushindo, thank you for both a very nice puzzle/challenge and a superb ah-ha trick . I was barking up the wrong trees when trying to divide it into smaller problems.

Edited December 17, 2010 by araver

[superprismatic]

Well, with a little fooling around, I have another function which all 12 people can use to get to a winning probability of

21/256 (or 336 times random guessing). The function's range (in order of 00000000 to 11111111 for the domain) is:

01111010111101101111011100101100111010010000011000000110111000011111110110000010100001111110110110000001101110001011010000000101

10111101100100001000000001101101010000001010111110111101111000111110000010010111110100100101000001101011001001000001010001101111