What color hat am I wearing?
... random thoughts , logic , math
tue 2005may10 15:07:22 pdt
... permalink
I recently wrote up (in an email to someone) a few of my favorite cute
little logicish 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 2player 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:
if at least one player is correct, both get a million dollars;
if both are wrong, they get nothing.
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 nplayer 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 j1, 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 3player game
As in the 2player 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:
if everyone wrote "no guess", they get nothing;
if at least one person made a guess and was wrong, they get
nothing;
if at least one person made a guess, and everyone who made a guess
was right, then they all get a million dollars.
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 3player 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.
mail me
