Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Cooperative games where a team of players must try to guess the color of their hat, but can only see their teammates' hats.

In these puzzles, a team of players are gathered, and one of several colored hats is placed on each of their heads. Without being able to see their own hat, each player must then guess what color their hat is. Before the game begins, the players may agree on a strategy, but after the hats are placed, no further communication is possible. Often, it is assumed the hats are chosen randomly.

NOT included in this tag are deduction puzzles where the perfectly logical participants are given information and then are asked to deduce their hat colors, like the four prisoners riddle or any of the blue-eyed islanders type puzzles. The appropriate tag for these is .

Though this framework sounds very specific, the solving these problems uses a wide variety of mathematical concepts, like modular arithmetic, Hamming codes, expected value of random variables, and permutations.

A classic example of such a problem is Hats and Aliens.

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.

history | excerpt history