Seven hat colours and a guaranteed correct guess
Question
Seven prisoners each receive a hat in one of seven colours (colours may repeat). Each sees the others' hats but not their own, and all write down a guess simultaneously without communicating. They are all released if at least one guess is correct. Can they agree on a strategy that always works?
Short answer
Yes. Number the colours – and the prisoners –. Prisoner guesses the colour that would make the sum of all seven hats . The true sum has exactly one residue, so exactly one prisoner is right.
Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 2.9 Proof by Contradiction, 'Rainbow hats', p.30; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solution