Problem of the Week 1193

Too Many Hats

There are 10 prisoners: Alice, Bob, Charlie, ..., Jill. The warden will call them together and line them up in order, with Alice first. He has 11 differently colored hats — all 11 colors are known to the prisoners — and will randomly place one hat on each prisoner's head, discarding the last one. Each prisoner can see the hats of only the prisoners in front of them; i.e., Alice sees all (except her own); Bob sees eight hats; Jill sees nothing.

At some point Alice will guess her color; all the other prisoners can hear her guess. Then the same for Bob, and so on to Jill. But a prisoner may never call out a color that has already been called out.

The prisoners will be freed if all guesses are correct. As always, the prisoners know all rules in advance and can devise a strategy.

Discover a strategy that maximizes the chance that the prisoners are freed.

Source: Tanya Khovanova, The Mathematical Intelligencer 36:3 2014, pp.44-46. Problem due to Konstantin Kopp and Alexander Shapovalov.

[View the solution]