Prisoners and Rainbow Hats Strategy

This brain teaser features a group of prisoners, each assigned a hat from a fixed set of distinct colors, who must independently guess their own hat color based only on what they can see on others. There is no communication once the hats are placed, and their survival depends on at least one correct guess. The core challenge is to agree on a strategy in advance that guarantees success regardless of how the colors are assigned, rather than relying on probability or luck. Variants of this setup, with different numbers of people or colors, often appear in math competitions, puzzle books, and logic-heavy interview rounds.

Solving it leans on encoding the visible information as numbers and reasoning modulo the number of possible colors. The key ideas involve partitioning the space of all hat assignments among the prisoners in a structured way, exploiting the fact that some aggregate function of the hidden and visible colors must take exactly one of several possible values. Interviewers watch for recognition of symmetry, the ability to formalize an informal puzzle into algebraic structure, and clear explanation of why the strategy is guaranteed rather than merely likely to work.

What it tests

This class of problems is governed by the principle of partitioning all possible outcomes among participants using modular arithmetic. By encoding each possible state (here, `hat color`) as a number and assigning each participant responsibility for one residue class modulo $n$, the group ensures that every possible configuration is covered. The key is that the sum of all unknowns modulo $n$ must be congruent to exactly one of the $n$ possible values, so if each person assumes the total sum is congruent to their assigned value, at least one will be correct. This works because the modular system partitions the outcome space perfectly and non-overlappingly, guaranteeing coverage. The principle holds because, for $n$ participants and $n$ possible states, the modular sum must land somewhere, and the strategy ensures every possibility is claimed by exactly one guess.