A riddle about guessing hat colours (which is not among the commonly known ones)

Question

This is a riddle I heard recently, and my question is if someone happens to know the solution. I'm asking this out of curiosity more than anything else.

So here it is. The riddle is one of the countless variations of the "prisoners have to guess their hat colour" puzzle. $n$ prisoners are put a hat on top of their head, which can be red or blue. The colours are chosen at random by $n$ independent fair coin tosses. Then each prisoner can guess their own hat colour (red or blue) or pass. The prisoners can see each other, but not hear each other's calls and of course they have no other means of communication. This means that each call can only depend on the other prisoners' hat colours. However, before the distributing of hats begins, the prisoners are told the rules and can agree on a strategy. The prisoners win iff no prisoner guesses wrong and at least one prisoner guesses right. Which strategy should the prisoners use so that the winning probability becomes maximal?

Some remarks:

• A simple strategy is that one player just guesses and all other players pass, so that the maximal probabilty is at least 1/2. For $n=2$ this strategy is optimal.
• For $n=3$, there is a strategy that wins in 6 out of 8 cases: When a player sees (red,red) he guesses blue, for (blue,blue) he guesses red, and otherwise he passes. More generally this shows that the maximal probability is at least 3/4 for $n\ge 3$.
• It's possible to show that any strategy fails for at least 2 hat colour configurations (unless $n=1$), which shows that the above strategy is optimal for $n=3$.
• For $n=4$ there are more than $10^{15}$ strategies, and for $n=5$ it's about $10^{38}$ strategies, making it quite infeasible to just use a brute-force computer program (maybe for $n=4$ it's possible when exploiting the obvious symmetries).
• When changing the rules slightly by forbidding players to pass, then the maximal winning probability is always 1/2. This is a nice little exercise.

Actually I heard the riddle only for $n=3$ and then thought about the general $n$. So it's entirely possible that there is no nice solution.

Answer 1

After writing up this answer I found this paper that comes to the same conclusions and also generalizes the problem to $q$ hat colours. I'm posting the answer anyway to have it here on math.SE in self-contained form.

---

As described in the Wikipedia article Gerry linked to and this book it references, an optimal strategy concentrates the wrong guesses onto as few configurations as possible. Each individual player guesses incorrectly exactly half the time if she doesn't pass, and ideally these incorrect guesses should all be concentrated on configurations where everyone guesses incorrectly whereas the correct guesses should ideally be spread out one per configuration.

Let's denote the set $\def\red{\text{red}}\def\blue{\text{blue}}\def\pass{\text{pass}}\{\red,\blue\}$ of hat colours by $H$ and the set $\{\red,\blue,\pass\}$ of guesses by $G$. Then a strategy for $n$ prisoners is a function $H^n\to G^n$ such that the $k$-th entry of the value doesn't depend on the $k$-th entry of the argument.

Given a strategy, we're interested in the proportion of vectors of $H^n$ for which the strategy prescribes a value which is not the constant $\pass$ vector and in which all non-pass entries match the corresponding entries in the argument. Let's call such vectors good and the others bad.

Adjacent to every good vector $g\in H^n$ is at least one bad vector $b\in H^n$ that differs from $g$ only in the hat colour of one of the prisoners who guess correctly for $g$ (of which there is at least one). Conversely, given a subset $S\subseteq H^n$ of bad vectors such that every vector is adjacent to at least one bad vector in this sense, we can make all other vectors good by assigning an adjacent bad vector to each of them (arbitrarily if there's more than one) and letting only the prisoner in whose entry the two vectors differ guess.

Thus, an optimal strategy is defined by a minimal subset $S\subseteq H^n$ such that all vectors in $H^n$ are adjacent to at least one element of $S$. Such a minimal subset is called a binary optimal covering code of length $n$ and radius $1$, and the number of vectors in such a minimal subset is denoted by $K(n,1)$. This table (linked to from this page) gives the known bounds on $K(n,1)$ up to $n=33$.

For $n=2^k-1$ the Hamming codes described in the article and the book are optimal binary covering codes with $2^{n-k}$ vectors, with winning probability $1-2^{n-k}/2^n=1-2^{-k}=n/(n+1)$. For other values of $n$, the values of $K(n,1)$ are only known up to $n=9$, and for $n$ a power of $2$; the lower bound for $K(27,1)$ was improved only recently.

Answer 2

The puzzle is discussed at http://en.wikipedia.org/wiki/Hat_Puzzle, in the section on Ebert's version and Hamming codes.