I am currently writing an essay on hat puzzles, and for the warm-up section I introduce some of the standard finite hat puzzles. One of these proceeds as follows:

You and two friends are each given a tan or gray hat, determined in each case by a coin flip. Nobody knows their own hat color, but everyone can see the other two. At the bell, everyone will either announce a guess as to their own color or remain silent. The three of you win, as a team, if at least one person guesses correctly and nobody guesses incorrectly. So you will lose if everyone is silent or if someone makes a wrong guess. What is your best chance of winning? You may arrange a strategy before the coins are flipped and the hats given out, but of course there is no communication allowed after that.

Of course you can win with at least fifty percent chance just by agreeing that a designated person says "tan" regardless, and nobody else says anything. But actually, you can do better by following the strategy: if someone sees two hats of the same color on the others, then guess the opposite color for yourself. This will be correct in 6 out of the 8 possibilities, if you think about it, so this is a 75% chance of winning.

My question is: how can we prove this solution is optimal?

I'd like to claim that no strategy directing the players to make an announcement or be silent can achieve a winning percentage greater than 75%, but I've realized that I don't actually know how to prove this.

9more comments