Four Hats

You and three friends are contestants on the newest edition of “Guess Your Hat.” As in previous editions of the show, you will each have a hat placed on your head. But now the hats can be one of four colors: red, yellow, blue or green. Some (or even all) of you may have the same color hat.

You can see everyone else’s hat but not your own, and your goal is to guess the color of your own hat. Everyone who guesses right wins, and everyone who guesses wrong loses. The guesses are made in private.

You can’t communicate with your friends in any way during the game, but you can communicate with them beforehand to decide on a strategy. However, the showrunners will be listening in, so they will know whatever strategy you decide on. They will then choose your hats in the worst possible way (for you), trying to make as many people as possible lose.

Given the behavior of the nefarious showrunners, you probably can’t pick a strategy that will let everybody win. But can you design a strategy that guarantees at least one of you will win? How about guaranteeing at least two winners?

(fivethirtyeight)

Solution

A distribution is an assignment of colors to the four players, and a scenario, representing the information a particular player has, is an assignment of colors to all but that player. A strategy is an assignment of colors (guesses) to scenarios.

There are four distributions for each scenario; whatever the strategy, the player of the scenario guesses correctly in one of them. So each player will guess correctly in exactly $1/4$ of the $4^4$, or $256$, distributions, and so overall there are $256$ correct answers spread out among the distributions. This shows that there is no strategy in which at least one player always guesses correctly and sometimes more than one does. Guaranteeing a single correct guess is the best we can do in principle. Can we do even that?

We can. Coding the colors as $0$ through $3$, let the actual colors of our player’s hats in a given distribution be $a,b,c,d$ and label the players $A,B,C,D$. The strategy is for the players to guess as follows (where addition and subtraction is modulo 4):

The idea here is that each player chooses the color such that, if their hat is that color, then the sum (modulo $4$) of all four actual hat colors is a specific, unique value: $0$ for player $A$, $1$ for $B$, and so on. That actual sum is always (for any distribution) some value between $0$ and $3$, and whichever value that is, the player who guesses the color that would give it that value guesses correctly. So if the actual sum is $0$, player A wins; if $1$, B wins; and so on.

There is nothing special about the number $4$ here–the technique will work for $n$ hats and colors for any $n$.