100 prisoners stand in a line, each wearing a hat of one of 10 colours. Each sees only the hats in front of him. Starting from the back, each names a colour aloud, and everyone hears all earlier guesses. They agree a strategy in advance. How many correct guesses can they guarantee?

100 prisoners stand in a line, each wearing a hat of one of 10 colours. Each sees only the hats in front of him. Starting from the back, each names a colour aloud, and everyone hears all earlier guesses. They agree a strategy in advance. How many correct guesses can they guarantee?

Approach: Have the prisoner at the back encode a single number about everything he can see, chosen so that each later prisoner can subtract what he sees and what he has heard.

99. Number the colours 0 to 9. The prisoner at the back adds the 99 colours he sees modulo 10 and announces the colour with that index. His own guess is a signal and is right only with probability 1/10. The next prisoner sees the 98 hats ahead, so he subtracts their sum from the announced total modulo 10 and recovers his own colour exactly. Every later prisoner subtracts both the hats he still sees and every colour already named, so all 99 are certain. No strategy saves all 100: the back prisoner's hat is independent of everything he can observe, so whatever he says is right with probability 1/10, and the guaranteed count is 99.

Follow-up: With the same 10 colours but each prisoner seeing only the single hat directly in front of him, how many can be guaranteed?

Key concepts: modular arithmetic, parity signal, guaranteed strategy.