Optimal Hat Strategy for Prisoners Using Parity

This puzzle presents a classic hat-guessing scenario involving many participants who can see everyone else's hats but not their own, and who must speak in sequence with no further communication. It asks candidates to design a pre-agreed strategy that maximizes the number of people who can be guaranteed to survive, even though the hats are assigned at random and the speaking order is unknown. The twist is that each spoken guess is public information for all remaining participants, so every statement can be used as a signal rather than a mere guess, turning a seemingly individual game into a coordinated group protocol. Variants of this style of question are common in brainteaser-heavy quantitative interviews and in theoretical computer science circles.

Solving it leans on modular reasoning, parity arguments, and thinking of information as something that can be encoded in a single constrained bit. The interviewer is looking for candidates who can define an invariant over the whole group, formalize it precisely, and then reason consistently under randomness and uncertainty. Good answers show comfort with combinatorial reasoning, clear articulation of the shared convention, and an understanding of how later speakers can logically reconstruct their own state from earlier signals.

What it tests

This problem class is governed by the principle of encoding global information into a single, observable signal that can be used as a reference by others. Specifically, it leverages the concept of parity (evenness or oddness) as a way to communicate a collective property (such as the total number of red hats) using only local observations and one bit of information. The key is that the first agent's statement is not just a guess, but a deliberate encoding of a property that everyone else can use to resolve their own uncertainty. This works because each subsequent agent has enough information (the initial signal and their own observations) to uniquely determine their own state, given the global constraint. The power of this approach lies in transforming a problem of individual uncertainty into one of collective certainty through a shared convention.