14

« **on:** February 04, 2020, 02:38:44 pm »
I found an optimal strategy:

Index the players 1-127.

Each player computes the XOR of the indices of the players with red hats.

If it is 0, they guess that they have a red hat.

If it is their own index, they guess that they have a black hat.

Otherwise, they abstain.

Thoughts on how to come up with this strategy:

Since each guess is correct with 50% probability, in order to maximize the chance of winning we need to make it so that when someone guesses wrong, everyone else does too, and when someone guess right they are the only one to guess.

The easiest example of this sort of behavior is a situation where a player guesses that they have a red hat if all other players have a black hat.

Then everyone guesses wrong if there are all black hats, and exactly one person guesses correctly if there is exactly one red hat.

Basically, we need to tile the space with clusters consisting of a center state (where everyone guesses wrong) and all the adjacent states.

Due to the way that switching a hat color twice doesn't change the state, it seemed natural to use some sort of XOR condition.

So, I picked the states where everyone guesses wrong to be the states where the XOR of the indices of red hats to be 0.

You could pick a different number besides 0 if you want.

That said, here is a similar problem from the most recent putnam:

Let Z^n be the integer lattice in R^n. Two points in Z^n are called neighbors if they differ by exactly 1 in one coordinate and are equal in all other coordinates.

For which integers n ≥ 1 does there exist a subset S of Z^n satisfying the following two conditions?

(1) If p is in S, then none of the neighbors of p is in S.

(2) If p is not in S, then exactly one of the neighbors of p is in S