There are 100 prisoners in jail. Their guards decide to play a game with them. Here's what happens:
1) The prisoners are lined up in a single file, front to back, such that the prisoner at the back of the line can see the 99 prisoners ahead of him, the prisoner immediately ahead of him can see the 98 prisoners in front of him and so on.
2) A randomly selected hat is placed on each prisoner's head. The hat may be black or white.
3) Starting from the back of the line (i.e. starting from the prisoner that can see 99 prisoners in front of him), a guard asks each prisoner what the colour of their hat is. If the prisoner answers correctly, he lives, otherwise, he is killed.
The prisoners are given these rules and then given 15 minutes to strategize before the game begins. What is the strategy that maximizes the expected value of the number of them that survive?
Can the prisoners take off their hats and look at them? No.
Do we know in advance how many of each colour hat there is? No.
Can the prisoners communicate with the other prisoners in any way apart from responding to the guard's question after the strategizing time is over? No.
Is an expected value of 75 survivors the best that can be achieved? Nope :)
Here's the strategy that gives an expected value of 99.5 survivors:
The prisoner at the back counts the number of white hats. If he sees an even number of white hats, he says "white" when asked by the guard, if he sees an odd number of white hats, he says "black" when asked by the guard.
The next prisoner to be asked (the one that can see 98 prisoners in front of him) can count the number of white hats ahead of him and, based on what the first prisoner said, determine whether he is wearing a white or black hat. Specifically, suppose the first prisoner answered "black", indicating that there is an odd number of white hats. Then, if the second prisoner's count is also odd, he must be wearing a black hat. If the second prisoner's count is even, he must be wearing a white hat.
Based on the previous responses, keeping track of whether they should expect an odd or even number of white hats in front of them, every prisoner can determine whether they are wearing a black or white hat.
Since the first prisoner is the only one who's response is up to chance, he has a 50/50 chance of survival. Everyone else has a 100% chance of survival, so we expect 99.5 of them to survive.
This is related to the concept of a parity bit used for error detection in computers.