You and six other friends are imprisoned by an evil genius, in a room filled with eight bubbling bottles marked as “poison.” (Though, really, seven of them look perfectly safe to you.) The evil genius, though, admires skill with bitstrings and computation, and offers you all a deal. You and your friends will each have a red or blue hat placed on your heads randomly. (Each hat has a 50% chance of being red and 50% chance of being blue, independent of all other hats’ colors.) Each person can each see all hats except his or her own. After a brief moment to look at each others’ hats, all of you must simultaneously say one of three things: red, blue, or pass. The evil genius will release all of you from your imprisonment if
• everyone who says red or blue correctly identifies their hat color; and
• at least one person says a color (that is, not everybody says pass).
You may collaborate on a strategy before the hats are placed on your heads, but once the hat is in place, no communication is allowed.
An example strategy: all 7 of you pick a random color and say it. (You succeed with probability (1/2)7 = 1/128 ≈ 0.0078.) Another example: you number yourselves 1, 2, . . . , 7, and person #7 picks a random color and says it; everyone else passes. (You succeed with probability 1/2.) Can you succeed with probability better than 1/2? If so, how?