Here's a neat little puzzle taken from a Google interview question:
10 humans are abducted by aliens; each represents 10% of the entire human population. The aliens give each abductee either a purple hat or a green hat. The 10 are lined up in a single file line, each facing forward, such that the last person can see the remaining 9's hats, the second to last person can see the remaining 8's hats and so on. No one can see his or her own hat.
The aliens then proceed, starting from the last person, to ask each of the abductees what the color of their hat is. If they guess correctly, they and the 10% of the human population they represent survives; if not, the opposite happens.
Assuming the abductees are given a chance to develop a strategy before they are lined up and questioned: what is the optimal strategy they can utilize (i.e. the one with the highest expected number of survivals)?
During the questioning, the abductees are not allowed to say anything besides their guess for the color of their hat when it is their turn.
The optimal strategy will always ensure 9 survivals, and will have a 50% chance of the 10th survival.