Three Colours of Hat

  • Hard
  • Game strategy puzzles
  • Tests: Sacrificing one player to inform everybody else

The puzzle

Ten prisoners stand in a line, each able to see the hats of everyone in front but not their own. The hats come in three colours, in any mixture. Starting from the back, each must say a colour aloud; saying their own colour saves them.

They may agree a plan beforehand. How many can they guarantee to save?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

The one at the back sees everything and can be sacrificed to carry a message.

Hint 2

With three colours, number them 0, 1 and 2 and work modulo 3.

Show the answer Hide the answer

Nine — everybody except the prisoner at the back, who has a 1 in 3 chance.

How to get there

Number the colours 0, 1 and 2. The prisoner at the back adds up the colours of all nine hats in front, takes the remainder on division by 3, and says the colour with that number. They are guessing their own hat blind, so they survive only by luck.

The next prisoner has heard that total and can see the eight hats in front. Subtracting the visible sum from the announced remainder, modulo 3, leaves exactly their own colour. They say it, and survive with certainty.

Everybody after that does the same, subtracting both the hats they can see and the colours already announced. Each answer is both a rescue and an updated message for those in front, so all nine are saved. The same scheme works for any number of colours, modulo that number - with two colours it is parity, which is the familiar version.

The technique worth keeping

Encode a global fact as a single remainder and let one player pay for broadcasting it. Everyone else subtracts what they can see from what was announced, and modular arithmetic makes that subtraction exact.