What color hat am I wearing?   ...   random thoughts , logic , math
tue 2005-may-10 15:07:22 pdt   ...   permalink

I recently wrote up (in an email to someone) a few of my favorite cute little logic-ish puzzles, involving guessing the color of the hat on one's head. As long as I'd already written them up anyway, I figured I'd post them here so that others may share the joy. I did not invent them, and I have no idea where the first two come from; the third I provide a reference for below.

These are cooperative games -- all players share the reward if they win and get nothing if they lose (in harsher versions of some of these, people get shot if they lose, I suppose for dramatic effect). The games are similar in structure, but the solutions are quite distinct. In (I think) increasing order of difficulty:

The 2-player game

Two players sit facing each other, each with a red or blue hat placed on her head; each can see the other's hat but not her own. Each player must write down a guess, "red" or "blue", for her own hat color, without knowing the other player's guess. The guesses are then revealed and:

They can of course agree on their strategy ahead of time but cannot communicate once the game begins. Obviously if they both just guess randomly, they win with 3/4 probability. But can you come up with a strategy that has a better chance of winning? Can you guarantee a win?

(yes/no answer to whether you can guarantee a win, with no explanation given)

The n-player game

n players line up, one behind the next, all facing north. Hats are placed on their heads. Thus player j can see the colors of the hats on the heads of players 1 through j-1, but not her own or those of players j+1 through n. In order from player n down to player 1, each player must guess her hat color, out loud. So player j has heard the guesses made by players n down to j+1 when she has to make her guess, but does not know which or how many of those earlier guesses were correct.

At the end, if k of the n guesses were correct, everyone splits k million dollars.

Again, the players agree on a strategy ahead of time but cannot communicate once the game begins.

Obviously if everyone guesses randomly, expected payoff is n/2 million. But with that strategy, in the worst case, everyone might happen to guess wrong, and they get nothing. So can you guarantee that some guesses are correct? Can you guarantee that strictly more than n/2 are correct? How close to all n can you guarantee?

(how close you can get to all n, with no explanation)

The 3-player game

As in the 2-player game, three players sit around a table, and each can see the other players' hats but not her own. Each player may then write down a guess, "red" or "blue", but this time they have the option to instead write "no guess". As before, all players must write down their guess (or lack thereof) without knowing what the other players have written. The guesses are then revealed and:

As always, they agree on strategy in advance but cannot communicate once the game begins. This time we will assume each hat color is selected uniformly at random. One simple strategy would be to decide that no matter what, player 1 will guess "red" and players 2 and 3 will write "no guess"; this gives a 1/2 chance of winning. Can you do better than 1/2? Can you guarantee a win?

(yes/no answer to whether you can guarantee a win, with no explanation given)

The generalization of the 3-player game to n players actually turns out to have real applications, and although it's solved for n = 2^k-1 players, the general case of n is (last I heard) an open problem. [Lenstra/Seroussi, 2002]

Please do NOT post solutions in the comments below. Thanks.

post a comment on this entry