Pirate Hat Puzzle: Cooperative Parity Strategy

Worked Solution

How to Think About It: The naive approach -- everyone guesses randomly -- gives $(1/2)^{10} \approx 0.1\%$, useless. The temptation is to imagine one pirate "announcing" a parity bit that the others then decode from his guess. That framing is illegal here: the guesses are made *simultaneously and independently*, and reading another pirate's guess would be communication, which is forbidden. No pirate ever learns anyone else's guess. Every pirate may use *only* the 9 hats he sees. The right idea is therefore fully symmetric: the group fixes one global parity convention in advance, and each pirate independently guesses the color that makes the observed-plus-own count obey that convention. With this rule all ten pirates are correct together or all wrong together, and they win exactly on the configurations whose true parity matches the convention -- which is half of them.

Quick Estimate: There are $2^{10} = 1024$ equally likely hat configurations. Any cooperative strategy is just a collection of functions, one per pirate, from "the 9 hats I see" to a guess. Focus on any single pirate, say pirate 1: his guess is a function of the other 9 hats, while his own hat is an independent fair coin he cannot see. So no matter how clever the strategy, pirate 1's own hat is equally likely to match or mismatch his guess -- he is correct with probability exactly $1/2$. Survival requires *everyone* correct, hence in particular pirate 1 correct, so $P(\text{survive}) \le 1/2$. The question is whether $1/2$ is actually reachable; parity shows it is.

Approach: (1) Naive: independence gives $(1/2)^{10}$. (2) Fix a global parity target for the total red-hat count; have *every* pirate independently guess the color that makes the total match the target, using only the hats he sees. Show all guesses are simultaneously right iff the true total has the target parity, an event of probability $1/2$. (3) Upper bound: any single pirate is right with probability exactly $1/2$ on his own hat, capping the group at $1/2$.

Formal Solution:

*Part 1 -- Naive strategy.* If each pirate guesses his own color by an independent fair coin, his guess matches his (independent, fair) hat with probability $1/2$. The ten events are independent, so $$P(\text{survive}) = \left(\tfrac12\right)^{10} = \frac{1}{1024} \approx 0.098\%.$$

*Part 2 -- Optimal strategy (symmetric parity).* Let $\mathrm{hat}_k \in \{0,1\}$ with $1 =$ red, and let $R = \sum_{k=1}^{10}\mathrm{hat}_k$ be the total number of red hats. Before the game the pirates agree on a target parity -- say, the total number of reds should be even. Now each pirate acts *independently*:

> Pirate $k$ counts the reds among the 9 hats he sees, namely $s_k = R - \mathrm{hat}_k$, and guesses the color of his own hat that would make the total even. Concretely he guesses red if $s_k$ is odd (so that adding his red makes the total even) and blue if $s_k$ is even.

No pirate observes any guess; each uses only his own observation $s_k$. Examine the two cases:

• $R$ even. For pirate $k$: if his hat is red then $s_k = R-1$ is odd, so he guesses red -- correct; if his hat is blue then $s_k = R$ is even, so he guesses blue -- correct. Every pirate is correct, so the group survives.
• $R$ odd. For pirate $k$: if his hat is red then $s_k = R-1$ is even, so he guesses blue -- wrong; if his hat is blue then $s_k = R$ is odd, so he guesses red -- wrong. Every pirate is wrong.

Thus the outcome is all-or-nothing and survival happens exactly when the true total $R$ is even. Since $R$ is a sum of 10 independent fair bits, its parity is uniform: $P(R\text{ even}) = 1/2$. Hence $$P(\text{survive}) = P(R \text{ even}) = \frac{1}{2}.$$ (Using the "odd" convention instead would make the group win exactly on the odd-parity configurations -- also probability $1/2$.)

*Part 3 -- Optimality (no strategy exceeds $1/2$).* Fix any cooperative strategy. Pirate 1's guess is some deterministic function $g_1$ of the 9 hats he sees, $g_1(\mathrm{hat}_2,\dots,\mathrm{hat}_{10})$. His own hat $\mathrm{hat}_1$ is generated by an independent fair coin and is invisible to him, hence statistically independent of everything $g_1$ depends on. Conditioning on the other 9 hats fixes the guess $g_1$ but leaves $\mathrm{hat}_1$ uniform on $\{$red, blue$\}$, so $$P(\text{pirate 1 correct}) = \tfrac12 \quad\text{for every strategy.}$$ Survival requires every pirate correct, in particular pirate 1, so $P(\text{survive}) \le P(\text{pirate 1 correct}) = 1/2$. (Counting check: for each of the $512$ assignments of the other 9 hats, $g_1$ is fixed, and exactly one of the two values of $\mathrm{hat}_1$ makes pirate 1 right; so pirate 1 is right in exactly $512$ of the $1024$ configurations.) The parity strategy attains this bound, so $1/2$ is optimal.

Answer: The naive strategy survives with probability $(1/2)^{10} = \boxed{1/1024}$. The optimal cooperative strategy has every pirate independently guess the color that makes the total number of red hats match a pre-agreed parity (e.g. even); all ten are then correct exactly on the even-parity configurations, giving survival probability $\boxed{1/2}$, and no strategy can do better because any single pirate is correct with probability only $1/2$ on his own hat.