Answer: Tuesday Teaser #6
Perhaps surprisingly, the best strategy will allow you to save 99 prisoners. To do this, we use a trick involving parity, which goes like so:
The prisoner at the back of the line can see 99 hats in front of him. Those hats are either white or black, so we have two possible scenarios - either there are an odd number of white hats and an even number of black, or there are an odd number of black hats and an even number of white. It is pre-agreed that the prisoner at the back will say the colour in which he can see an odd number of hats. Let’s suppose this colour is black. The prisoner in front of him, who can see all of those 99 hats except his own, can now count up the number of black hats in front of him. If there are an odd number, his must be white, and if there are an even number, his must be black. In this way, each prisoner in turn can work out what the colour of their own hat must be simply by tracking the parity (odd or even-ness) of the number of black hats.
Therefore, as long as there is someone willing to sacrifice himself to a 50-50 chance of survival, you can guarantee that 99 prisoners will be saved. It’s worth noting that because nobody can see the colour of the last prisoner’s hat, it is impossible to guarantee the survival of all 100 - so 99 is the best we can do.
