Two prisoners are told that they will be brought to a room and seated so that each can see the other. Hats will be placed on their heads; each hat is either red or green. The two prisoners must simultaneously submit a guess of their own hat color, and they both go free if at least one of them guesses correctly. While no communication is allowed once the hats have been placed, they will, however, be allowed to have a strategy session before being brought to the room. Is there a strategy ensuring their release? The answer turns out to be yes, and this is the simplest non-trivial example of a...