A hat puzzle question—how to prove the standard solution is optimal?

Question

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.

Answer 1

Suppose we have some mixed strategy for this hat puzzle. For each of the $8$ possible hat assignments and each of the $3$ people involved, we can ask about the probability that the person guesses correctly conditional on that hat assignment, and the probability that they guess incorrectly. After specifying this, we'll have assigned a probability to every possible (world state, person 1 accuracy, person 2 accuracy, person 3 accuracy) tuple, where the world state can be in one of 8 arrangements, and each person's accuracy can be graded as "correct", "silent", or "incorrect".

For a single person, their expected probability of being correct (conditional on venturing a guess) is always 0.5 - that is, the total probability of all outcomes in which they guess correctly must equal the total probability of all outcomes in which they guess incorrectly.

In order for an outcome to lead to a success, we need at least one correct guess and no incorrect guesses. So the probability of success in the puzzle is at most the sum of P(correct) across all three people.

Meanwhile, an unsuccessful outcome can have at most three incorrect guesses, because there are only three people. So the probability of failure is at least one-third as large as the sum of P(incorrect) across all three people.

But for each person, P(correct) = P(incorrect)! So we know that the success probability is at most three times the failure probability, which bounds our success rate by 0.75.

Answer 2

Suppose you and your two friends have names A, B, C.

For each case, assign a 3-letter string for what colours the people get. For example, TGG means A gets tan while B and C get gray.

Suppose when A sees two tan hats, there is probability $A_T$ that A guesses tan.
When B sees two tan hats, there is probability $B_T$ that B guesses tan.
When C sees two tan hats, there is probability $C_T$ that C guesses tan.

$Pr(\text{win|TTT})\le\text{expected number of correct guesses}=A_T+B_T+C_T$
$Pr(\text{win|GTT})\le1-A_T$ since there is probability $A_T$ that A guesses wrong
$Pr(\text{win|TGT})\le1-B_T$ since there is probability $B_T$ that B guesses wrong
$Pr(\text{win|TTG})\le1-C_T$ since there is probability $C_T$ that C guesses wrong

Therefore, $Pr(\text{win|TTT})+Pr(\text{win|GTT})+Pr(\text{win|TGT})+Pr(\text{win|TTG})\le3$ so $Pr(\text{win|at least two tan})\le3/4$. Similarly, $Pr(\text{win|at least two gray})\le3/4$ so $Pr(\text{win})\le3/4$.

Answer 3

There are 8 states of the world. Suppose that (with deterministic strategies) they win in 7 of those 8 states.

Then they either win in every state where A's hat is gold or in every state where A's hat is tan. Assume the former.

It follows that A never guesses tan. Likewise there is a color that B never guesses and a color that C never guesses. Let the colors they never guess be X, Y, Z. It follows that they lose in the state XYZ, so (because they win in 7 states) they must win in all other states.

Now consider what happens in the state X'Y'Z' (with all colors changed to their opposites). This is not the same as XYZ, so they must win in this state, which means somebody guesses correctly in this state. Let it be A. Then whenever A sees Y'Z', they must guess X'. But then they're wrong half the time.

Edited to add: Similar reasoning (and/or a generalization of RavenclawPrefect's argument) shows that the probability of a win is bounded above by $n/(n+c-1)$ when there are $n$ players and $c$ equally likely hat colors.

Answer 4

I'm making this a separate answer though it's really just a concise version of my earlier one:

Suppose there are 7 winning states. Let XYZ be a winning state in which both A and B name colors. Then X'YZ and XY'Z are both losing states, contradiction. Therefore in any winning state, at most one player names a color. Therefore there are at most 4 winning states (indexed by the possibly empty set of players who name colors in that state), contradiction.

Answer 5

In October 2023, a book was published that is entirely about hat puzzles. The answer to your question is also in it. The title of the book is "De kabouterformule" ("The Gnome Formula"). The book, published by Prometheus, is written in Dutch, but if you have the e-book, you can perhaps have it translated automatically? (The author of the book is myself, apologies for this shameless self-promotion.)

Answer 6

Consider the game with $n$ players, and identify the possible assignments of hat colours with vertices of the $n$-dimensional hypercube graph. Given a (deterministic) strategy, let $S$ be the set of vertices where the strategy suceeds.

I claim that for any vertex $v$, the $n+1$ vertices in $N^+(v)=\{v\}\cup N(v)$ cannot all be included in $S$: if $N^+(v)\subseteq S$, then in situation $v$, the strategy must make everybody silent, as any possible anouncement of the $i$th player is inconsistent either with $v$ or with the $u\in N(v)$ that differs from $v$ in $i$th coordinate. But then the strategy fails in $v$ after all, a contradiction.

This implies $$|S|\le\frac n{n+1}2^n:$$ if the probability that a randomly chosen vertex $v$ belongs to $S$ is $p>n/(n+1)$, then by linearity of expectation, the expected number of elements of $N^+(v)\cap S$ is $(n+1)p>n$, thus there exists a vertex $v$ such that $|N^+(v)\cap S|\ge n+1$, a contradiction.

For $n=3$, we get $|S|\le6$.

Conversely, if $S$ is a set of vertices such that $N^+(v)\nsubseteq S$ for all $v$, then there exists a strategy that succeeds on $S$, defined as follows. For a given player, let $u$ and $v$ be the two neighbouring vertices consistent with what the player observes. If exactly one of $u$ and $v$ belongs to $S$, say $w$, let the player announce the colour corresponding to $w$; otherwise the player remains silent. If $v\in S$, then in situation $v$, no player can announce an incorrect colour, and the condition $N^+(v)\nsubseteq S$ ensures that all players cannot remain silent.

Answer 7

Assume you have a strategy winning on at least $7/8$ cases.

Each player can see $4$ configurations, and whenever they speak on a certain configuration, they lose with probability $50$%. It follows that every player can speak at most in one configuration.

But then there are at least $8 - 3 \times 2 = 2$ cases in which all players are silent, and hence they lose, contradiction.