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

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.

• puzzling.stackexchange.com/questions/tagged/hat-guessing Commented Jul 24 at 0:18
• It doesn't say that the three people are men, but, if they are, we can call this the Man-hat-tan puzzle. Commented Jul 24 at 2:28
• @GerryMyerson There are times when I wish the system allowed us to downvote comments.
– bof
Commented Jul 24 at 3:51
• @bof, the system does allow us to flag comments for moderator attention. Commented Jul 24 at 4:22
• @bof: You could always ignore my.. err.. son... Commented Jul 25 at 8:01

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.

• Since I win for every row with at least one "correct" and no "incorrect"s, the best I can hope for is to get 6 rows with a single "correct" and 2 rows each with three "incorrect"s - because if I had 7 or more rows used up on being correct, I wouldn't have room to fit my ≥7 incorrect guesses. Commented Jul 23 at 23:18
• Here's a simple table of this allocation in the standard solution; we have 6 correct answers and 6 incorrect answers, distributed across 6 and 2 world states respectively. Commented Jul 23 at 23:23
• @bof The three-person strategy can be generalized to an approach which saturates this bound whenever the number of participants is one less than a power of $2$. Given a Hamming code on strings of length $2^n-1$, each person ventures a guess only if what they see is compatible with the arrangement forming a codeword, and guesses whichever color on their hat would not lead to a codeword. Since all strings are either a codeword or exactly one bit-flip away from a codeword, this leads to success on all non-codeword inputs. Commented Jul 24 at 4:18
• Excellent answer, it gives insight into this class of problem where you want no failure in order to win : you have to fail as hard as you can on a few bad cases. (Here all 3 players fail at the same time, allowing them to win on 3 different games) Commented Jul 24 at 7:55
• I find all the mixed strategy stuff an irrelevant distraction. The main point I take is: every instance of someone guessing correctly must be balanced by an instance of that person making the same judgement but being incorrect. So if we win six rows, there must be at least six instances of incorrect guess, and this uses up the remaining slots in the other two rows. So winning seven is impossible. Commented Jul 24 at 16:11

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$$.

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.

• I'm confused. You say, assuming the supposed 7/8 strategy wins whenever A is gold, that it follows A never guesses tan. But why is that exactly? Perhaps A does so in two cases, one of which is the 1/8 losing case, and the other is part of the winning 7/8. Commented Jul 24 at 0:43
• Note: my colors were tan/gray, not gold. Commented Jul 24 at 0:44
• @JoelDavidHamkins : A never guesses tan in any of the cases GGG,GGT,GTG,GTT. But A's guess can only depend on B's and C's hats, so he also never guesses tan in TGG,TGT,TTG,TTT. Commented Jul 24 at 1:27
• Ah yes, I see. Very clear. Commented Jul 24 at 1:46
• @JoelDavidHamkins : I should add also that there's clearly no advantage to randomizing. Let STU be a triple of strategies that maximizes the probability of a win. Call that probability p. Then clearly no probability distribution over triples of strategies can yield a probability higher than p. Commented Jul 24 at 1:52

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.

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.)

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.

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.