A group of 25 codebreakers is captured. Each receives a black or white hat and can see every other hat but not their own. At a single signal, they all guess their own colour simultaneously. Correct guesses go free.
Two rules make this adversarial rather than cooperative. The Overlord knows the agreed strategy in advance and assigns hats to minimise the number freed. And once the hats are placed, no communication is allowed.
How many can you guarantee to save?
Note: This is the simultaneous version. In the sequential variant, players answer one at a time and hear every earlier answer.
Start with two codebreakers. The obvious plan - guess the colour you see on the other - fails immediately: the Overlord knows the plan and hands out opposite colours. Both stay imprisoned. More generally, if a player commits to any fixed response to the single visible hat, the adversary counters it, because the adversary moves last. Whatever you can compute, the Overlord has already computed. Nothing is guaranteed yet.
Suppose each player privately flips a coin: heads, guess the colour you see; tails, guess the opposite. For any hat assignment, the four coin outcomes save 2, 1, 1 and 0 codebreakers - the same multiset every time. Across all sixteen equally likely scenarios, this gives E[X] = 1 and Var(X) = 0.5. On average, one person walks free. But with probability 1/4, nobody does. An expectation is a statement about many games; a guarantee is a statement about the worst single one - and the Overlord only needs you to be unlucky once.
Write black = 0 and white = 1. The total number of white hats is either even or odd - one global fact the players can split between them. Player 1 always assumes the total is even and guesses accordingly; player 2 assumes odd. Check the four assignments - bb, bw, wb, ww - and exactly one player is right in every case. Both being wrong is impossible. The Overlord is trapped: X = 1 is guaranteed for n = 2, and no coin was flipped.
The parity pair is a self-contained machine, so split 25 codebreakers into 12 pairs, with one player left over guessing a fixed colour. That guarantees X ≥ 12. The matching upper bound is a counting argument: any fixed player sees an identical scene in exactly two configurations - own hat black, own hat white - so no player can be correct in more than half of all 2²⁵ configurations. Summing over 25 players caps the total correct guesses at 25 · 2²⁴, an average of 12.5 survivors per configuration. If the average is 12.5, some configuration yields at most 12, and the adversary chooses exactly that one. X = 12, and it is optimal. The construction is Winkler's [1]; the bound is Theorem 2 of Butler, Hajiaghayi, Kleinberg and Leighton [2].
Optimal play leaves the 25th codebreaker doing nothing - which is only right if the adversary is flawless. Suppose instead that hats are assigned white with probability p rather than adversarially. The spare player can now use the 24 visible hats. I tested three rules - simple majority, weighted majority, and a group-partition majority - over 200 million Monte Carlo trials per bias level. The means land above 12 everywhere (12.50 at p = 0.5); the observed minimum is exactly 12 in every case. The mean is just 12 plus the probability the spare player guesses right, so it lives strictly between 12 and 13 and can never reach 13. The extra player improves the average against a careless adversary. The worst-case floor never moves.
In a quant interview, the number 12 is not the point. The point is how you engineer through the traps. The first trap is the adversary that sees your strategy before placing a single hat, so anything clever you prepare is already priced in. The second trap is the average: coin-flipping saves one person per game on average, yet a quarter of the time it saves nobody - and you only play once. The average is what a strategy looks like; the minimum is what it guarantees. Parity is the way out because it needs no communication, and it turns the worst case itself into the thing you control.
The full essay is free: the n = 2 tables worked out line by line, the parity check across every assignment, the optimality proof in detail, and the complete Monte Carlo code - PCG64DXSM, 200 million trials per bias level, with the engineering choices explained. Enter your email on the home page - https://quanted.ai/ - and it arrives as a PDF.
1. Winkler, P. (2002). Games people don't play. In D. Wolfe & T. Rodgers (Eds.), Puzzlers' Tribute: A Feast for the Mind (pp. 301-313). Boca Raton, FL: CRC Press.
2. Butler, S., Hajiaghayi, M. T., Kleinberg, R. D., & Leighton, T. (2009). Hat guessing games. SIAM Review, 51(2), 399-413.