A hundred people are held captive in a prison by a small-scale dictator. They are all very intelligent, and while away their days creating and solving logic puzzles. Each one is assured of all the others’ strong logical abilities.
One morning, the warden tells the hundred prisoners that the dictator wants to close down the prison, so each prisoner must either be executed or released. Since there are no records on why any of the prisoners are there, the warden has decided to make his decisions on the basis of a game. At 7am the next morning, all the prisoners will be lined up in front of the wall in the courtyard and blindfolded. Then, three guards will walk behind the row of prisoners, putting one hat on each. Some hats will be red, some will be yellow, and some will be blue, in whatever proportions the guards decide to use. Once all the hats have been put on the prisoners, the first prisoner will have his blindfold removed and will be led slowly down past the other prisoners. Then, after he has seen everyone else’s hat, he will be asked the colour of his own hat. If he answers correctly, he will be released. If he doesn’t, he will be shot. Either way, his hat will be placed on the ground on the spot where he stood, so that the other prisoners can see it. The same thing will then happen to the second prisoner, then the third, and so on down the line, with every prisoner in turn having his blindfold removed, being able to see each other prisoner or the hat he left behind, and then having to guess his colour: a correct answer securing release, an incorrect one leading to death.
The warden makes clear that each prisoner will be permitted to hear each other prisoner’s guess, but that this is the only information that can be conveyed from one prisoner to another. If any other attempt is tried to get across information — if any prisoner modulates his voice, or scuffs his feet, or does anything else to transmit any message to another prisoner — then the game will end and all the prisoners will be executed.
For the rest of that day and through the night, the prisoners puzzle over what they should do. At worst, each of them has a 1/3 chance of being released: he merely has to guess at random. But they can do better than that, since there is a way for them to transmit information to one another while doing nothing more than making their guess. For instance, if there were only two prisoners, the first could see what colour the second prisoner’s hat is. Suppose it were red. Then, the first prisoner could guess “Red”, and the second prisoner (having already prearranged this system with the first) would then be guaranteed his release, since he would be bound to get the answer right. The first prisoner, meanwhile, would be stuck with a 1/3 guess, since he would only survive if his hat happened to be red as well.
So, there are ways of guaranteeing the release of some of the prisoners. The question is, how many prisoners’ releases can be guaranteed using the best method? 33? 50? 75? More? And, of course, what is the best method?