I think this was on Car Talk or something like that, so if you've heard it, please don't answer. Feel free to comment, but don't ruin it for everyone else! If you're really considerate, you could post the answer in rot13.
A prison guard is in a dilemma. His prison is full and he has a new shipment of prisoners due to arrive within a few days. To clear out the prison, he picks 10 random inmates. He can't decide whether he should let them go or to kill them, so he decides to put their fate into their own hands. He invents a game. Each prisoner is placed in a chair that's in a straight row. Then, a hat of either green or red is placed on each prisoner's head. He then tells them: each one of you is to guess which color your hat is. If you're right, then you're free to go; if not or you say anything other than your hat color, I shoot you on the spot.
The rules of the game are given to the prisoners the night before the game takes place. The guard gives them the chance to converse before the event as to maximize the number of prisoners allowed free.
Goal: Maximize the number of prisoners that live by inventing a strategy that can be used.
Rules:
* The prisoners can only say "red" or "green." If anyone does anything else, the guard shoots all of them.
* The prisoners can't look at their own hat colors or turn around to see other prisoners' hats. If this happens, the guard kills all of them.
* Each prisoner only has one chance to speak a color. He can say "red" or "green" once and then their turn is over.
* The prisoners are asked their hat colors sequentially, starting with prisoner 0.
* Each prisoner must answer immediately after his turn begins or they're shot.
Here are a few pseudo-hints:
* The diagram is a mere representation of a possible configuration of hats. The order and number of each color is purely random.
* The prisoner in the first seat can see all hat colors but his own. Prisoner 1 can see prisoners 2-9, etc.
