As people die they sometimes go to hell. The devil, the nice bloke that he is, gives them a chance to escape and go to heaven.
He lines them up outside the gates of hell and gives them each a black or white, with colors distributed randomly. No one gets to see the color of their own hat, but they can see the hats of everyone in front of them.
The devil approaches the person standing last in the line an asks for the color of his hat. If the answer is correct he escapes; if not, his stay in hell is final. The devil then proceeds to the next-to-last person in the line, and so on.
One hundred people have now died and they decide to come up with a strategy to help as many of them as possible to escape into heaven. They know that when they stand in line the only words the will be able to say are ‘black’ and ‘white’.
What strategy should they use? How many can be saved?
Please note: When they stand in line, everyone can see only the people in front of them, but everyone can hear the people behind them’s answer to the devil. Also note that the person last in line can never be saved for sure. No one but the devil knows his color.
Answer
The first attempt might be to have every odd-numbered person say the color of the person in front of them, and the evens saying the color they heard from the person behind them.
This saves at least fifty people, but we can do better.
Another solution might be to have the last person say black if the two people in front of him have the same color on their hats, and white if they don’t. The next person can then figure out his color by using that information together with the color of the one in front of him. And the person after that can use the two preceding answers to figure out his color.
This way we save two thirds of the people. But we can do better.
The last person can count the number of black hats he sees. If the number is even, he answers black; if it’s odd, he answers white. The next person can then also count the number of black hats he can see. If it is even and the last person said black, he must have a white hat. If it is odd, he must have a black hat for the number to become even to the one behind. This can be continued, where the next person also counts, and uses the answers of the people behind to make the numbers even out.
This saves 99 people.