Wayne sprung this question on me yesterday. I swear he should have been a CS major.

The Hundred Hatted Prisoners

There are a hundred prisoners in a dungeon, sentenced to be executed the next morning. Fortunately for them, the king of the land is eccentric and offers them a chance to survive. He tells them he’ll line them up, one in front of the other, with the most guilty in the back and the least guilty in the front. They’ll be bound, so it will be impossible for them to see those behind them, but they’ll be facing down a gentle slope and will be able to see all the prisoners in front of them clearly.

Next, the king will place a hat on the head of each prisoner. Some hats will be blue and some will be red, but the exact number of each is secret. The prisoner in the very back will be able to see which color of hats the other ninety-nine prisoners are wearing. The second prisoner will be able to see the hats of the ninety-eight prisoners in front, but not his own or the one on the prisoner in the back. It will continue like this, up to the prisoner at the very front of the line, who cannot see any of the hats.

Finally, the king will walk up the line, starting from the back, going to the front, asking each prisoner what color his own hat is. Anyone who answers incorrectly will be executed immediately, via silent odorless methods undetectable to those who haven’t yet been asked what color their hats are.

The prisoners may talk with each other tonight and collude to create a strategy for the next day. Once they are lined up for execution, though, they will not be allowed to speak, except to answer the king when he asks, “What color is your hat?” Even then, they may only utter a single word, “red” or “blue”.

If the prisoners work together with the right strategy, how many need to risk their lives?

This logic puzzle doesn’t really have a “sucker answer” like the coin-tossing one did, but the answer is a smaller number than one might first think. It’s a smaller one than I first thought.