[bushindo]

Suppose you and 4 friends are invited to play a game. The game is a variation of the hat puzzle with monetary incentive. The game is as follows:

1) You and your 4 friends each pay 10 dollars to participate in the game (50 dollars total).

2) All participant is then blind folded and have either a red or blue hat placed on each of their heads.

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

4) The blindfolds are removed, and each participant can look at the hat of his two immediate neighbors.

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

6) The game host then looks at all the guesses. If they are ALL correct, the 5 participants win a sum of 1000 dollars (20 times the money required to play the game). If one or more guesses are incorrect, the participants lose the 50 dollars.

7) Any attempt to cheat ( trying to exchange information through words, utterances, signs, facial expressions, delays in writing their answer, etc.) will lead to disqualification and forfeiture of the 50 dollars.

Obviously, if you and your 4 friends each randomly guess, your change of winning is 1/2⁵ = 1/32. Over about 30 such games, your group will shell out 1500 dollars while winning an expected 1000 dollars only. Fortunately, there are better strategies than random guessing. Determine a strategy that will give you and your friends positive expected winnings in the long run. (Bonus) What is the strategy with the highest expected winning?

Edited December 12, 2010 by bushindo

[araver]

Assume a deterministic strategy that wins in N cases out of 32. Then after 32 rounds with all the 32 possibilities you get N*1000 + (32-N)*(-50) = 1050*N-32*50 = 1050*N-1600.

Now if N>=2 then the strategy is positive in the long run.

Simplest positive strategy with N=2 is to always guess the color of the person to the left of you. This always wins in 2 out of 32 cases (RRRRR and BBBBB). Therefore it wins 500 dollars per 32 games, in the long run.

Found a rather asymmetrical strategy with N=4. Not sure if N>5 strategies are possible (I was not able to get past N=4).

Edited December 12, 2010 by araver

[pdqkemp]

Assume a deterministic strategy that wins in N cases out of 32. Then after 32 rounds with all the 32 possibilities you get N*1000 + (32-N)*(-50) = 1050*N-32*50 = 1050*N-1600.

Now if N>=2 then the strategy is positive in the long run.

Simplest positive strategy with N=2 is to always guess the color of the person to the left of you. This always wins in 2 out of 32 cases (RRRRR and BBBBB). Therefore it wins 500 dollars per 32 games, in the long run.

Found a rather asymmetrical strategy with N=4. Not sure if N>5 strategies are possible (I was not able to get past N=4).

I am not great with these puzzles, but your post got me thinking of something:

If you ONLY guess the person to your left, then that does give you 2 out of the 32 whenever everyone is Blue or everyone is Red. But that means, on the times when the person to your left is a DIFFERENT color than the person to your right, you have a ZERO chance of winning. Even if YOU are right about your color being the same as the person to your left, you know that the person to your right will end up being wrong by writing down your color which is similar to the color of the person to your left.

What would happen if you always planned on writting down the same color as the person next to you ONLY when BOTH your neighbors had the same color as you?

When your left neighbor is wearing an opposite color as your right, you ought to still give yourself a little bit of a chance, so you should guess randomly that time.

I just can't mathematically figure out how much more of an advantage that gives you if you plan on guessing during the times when your neighbors are wearing opposite.

[bushindo]

Assume a deterministic strategy that wins in N cases out of 32. Then after 32 rounds with all the 32 possibilities you get N*1000 + (32-N)*(-50) = 1050*N-32*50 = 1050*N-1600.

Now if N>=2 then the strategy is positive in the long run.

Simplest positive strategy with N=2 is to always guess the color of the person to the left of you. This always wins in 2 out of 32 cases (RRRRR and BBBBB). Therefore it wins 500 dollars per 32 games, in the long run.

Found a rather asymmetrical strategy with N=4. Not sure if N>5 strategies are possible (I was not able to get past N=4).

Great! Now we can show that we have positive expected winnings. The bonus question about the optimal strategy is still open though. I'd like to hear about your N=4 strategy.

[araver]

Great! Now we can show that we have positive expected winnings. The bonus question about the optimal strategy is still open though. I'd like to hear about your N=4 strategy.

Assume the 5 hats are a1a2a3a4a5 and they say b1b2b3b4b5.

The following is the strategy:

b1=a5

b2=a3

b3=a2

b4=a5

b5=a4

They win on 00000, 01100, 10011, 11111 hence N=4.

It's not so special in the sense that I don't see a deterministic expansion of this simple pairing idea.

Edited December 12, 2010 by araver

[araver]

I am not great with these puzzles, but your post got me thinking of something:

If you ONLY guess the person to your left, then that does give you 2 out of the 32 whenever everyone is Blue or everyone is Red. But that means, on the times when the person to your left is a DIFFERENT color than the person to your right, you have a ZERO chance of winning. Even if YOU are right about your color being the same as the person to your left, you know that the person to your right will end up being wrong by writing down your color which is similar to the color of the person to your left.

What would happen if you always planned on writting down the same color as the person next to you ONLY when BOTH your neighbors had the same color as you?

When your left neighbor is wearing an opposite color as your right, you ought to still give yourself a little bit of a chance, so you should guess randomly that time.

I just can't mathematically figure out how much more of an advantage that gives you if you plan on guessing during the times when your neighbors are wearing opposite.

And I'm not great with probabilities, but...

Your strategy with flipping a coin when neighbors differ gives N=2.625 (overall 2.625/32 win cases).

Besides my basic 2 cases, you win in 1/16 of the flips for 11000,01100,11100,00110,01110,10001,11001,00011,10011,00111

The same idea applied to my N=4 strategy gives no improvement (due to symmetry).

My hunch so far is that for this problem, an optimal deterministic strategy will be as good (or maybe better) than any non-deterministic strategy (involving randomness). I am a little biased since I personally do not enjoy probability theory.

I'm not sure what impact symmetry has on the game. So far it seems a certain degree of asymmetry is equivalent to randomness (flipping a coin randomness) which is again equal to a sort of symmetry

[bushindo]

And I'm not great with probabilities, but...

Your strategy with flipping a coin when neighbors differ gives N=2.625 (overall 2.625/32 win cases).

Besides my basic 2 cases, you win in 1/16 of the flips for 11000,01100,11100,00110,01110,10001,11001,00011,10011,00111

The same idea applied to my N=4 strategy gives no improvement (due to symmetry).

My hunch so far is that for this problem, an optimal deterministic strategy will be as good (or maybe better) than any non-deterministic strategy (involving randomness). I am a little biased since I personally do not enjoy probability theory.

I'm not sure what impact symmetry has on the game. So far it seems a certain degree of asymmetry is equivalent to randomness (flipping a coin randomness) which is again equal to a sort of symmetry

I agree with araver that probabilistic methods can not beat deterministic methods. With some thoughts, it seems that 4/32 as the winning rate is the best we can do with this situation. It is possible to extend the deterministic ideas to more general cases, but for this case with 5 players, it is not necessary and the puzzle is not as challenging as I intended to be. Puzzle making is quite tough . Let me go back and reconstruct this puzzle.

Edited December 12, 2010 by bushindo

[wolfgang]

we have only 8 possible arrengements:

00000,10000,11000,10100,11100,11010,11110 and 11111

except for( 00000) and (11111), each of the other forms is repeated 5 times.

Thus,there are 15 times (0)between two(1),while only 11 times (1) between two (1).

and there are 15 times (1) between two (0),and 11 times

(0) between two (0).

There are 30 times(1,0)between (0),where as only 25 times(1,0) between (1).

conclusion:

for each player to see two (1) he should write (0)

if he saw two(0) he should write (1),

if he saw two different colors,he should write(0)

I think,in this case we can reach a higher percentage.

[araver]

we have only 8 possible arrengements:

00000,10000,11000,10100,11100,11010,11110 and 11111

except for( 00000) and (11111), each of the other forms is repeated 5 times.

Thus,there are 15 times (0)between two(1),while only 11 times (1) between two (1).

and there are 15 times (1) between two (0),and 11 times

(0) between two (0).

There are 30 times(1,0)between (0),where as only 25 times(1,0) between (1).

conclusion:

for each player to see two (1) he should write (0)

if he saw two(0) he should write (1),

if he saw two different colors,he should write(0)

I think,in this case we can reach a higher percentage.

Your strategy is actually logical NOR.

And it does achieve N=5: 10100, 10010, 01010, 01001, 00101.

Equally a NAND strategy achieves N=5: 11010, 10110, 10101, 01101, 01011.

Edited December 13, 2010 by araver

[araver]

Your strategy is actually logical NOR.

And it does achieve N=5: 10100, 10010, 01010, 01001, 00101.

Equally a NAND strategy achieves N=5: 11010, 10110, 10101, 01101, 01011.

As I was not 100% certain, I wrote a program that checks all 2^20 possible deterministic functions - as for each of the 5 players there are 4 possible neighbor combinations. An individual player strategy can be modeled as an independent function of the neighbor combinations. So each deterministic global strategy can be seen as a 5-uple (f1,f2,f3,f4,f5) where fi's are functions corresponding to the 4 possible neighbor combinations.

No surprise:

- There is no function with N>5.

- There are 32 such functions with N=5. Each fi (i=1..5) is one of the 8 possibilities of biased functions with either 3-1s and 1-0s or 3-0s and 1-1s (including NAND, NOR, AND, OR and 4 other asymmetrical boolean functions which are less known).

Surprisingly (for me):

- the only symmetrical functions (f1=f2=f3=f4=f5) with N=5 are NAND and NOR (i.e. in which all players have the same individual strategy, no predetermined arrangement/convention is needed).

- As a corollary (after seeing the 32 possible functions), without establishing a common strategy before the game, the players cannot achieve such a perfect deterministic strategy (other than by accident). E.g. no other combination of NANDs and NORs is a perfect strategy (other than all NAND or all NOR) so if they don't decide a priori, they are more likely to choose fi's that don't yield a perfect f strategy.

Edited December 13, 2010 by araver

[bushindo]

As I was not 100% certain, I wrote a program that checks all 2^20 possible deterministic functions - as for each of the 5 players there are 4 possible neighbor combinations. An individual player strategy can be modeled as an independent function of the neighbor combinations. So each deterministic global strategy can be seen as a 5-uple (f1,f2,f3,f4,f5) where fi's are functions corresponding to the 4 possible neighbor combinations.

No surprise:

- There is no function with N>5.

- There are 32 such functions with N=5. Each fi (i=1..5) is one of the 8 possibilities of biased functions with either 3-1s and 1-0s or 3-0s and 1-1s (including NAND, NOR, AND, OR and 4 other asymmetrical boolean functions which are less known).

Surprisingly (for me):

- the only symmetrical functions (f1=f2=f3=f4=f5) with N=5 are NAND and NOR (i.e. in which all players have the same individual strategy, no predetermined arrangement/convention is needed).

- As a corollary (after seeing the 32 possible functions), without establishing a common strategy before the game, the players cannot achieve such a perfect deterministic strategy (other than by accident). E.g. no other combination of NANDs and NORs is a perfect strategy (other than all NAND or all NOR) so if they don't decide a priori, they are more likely to choose fi's that don't yield a perfect f strategy.

Thanks for the comments, araver. They are insightful as always. I have another challenging puzzle of this type that you might enjoy. I'll post that puzzle up after my current puzzle 7 Britishmen, 7 Frenchmen, and 7 Italians is solved. That shouldn't take long . Stay tuned.