What color hat am I wearing?
... random thoughts , logic , math
tue 2005-may-10 15:07:22 pdt
... permalink
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?
You can guarantee all but the very first guess. That is, you
can ensure a win of at least n-1 million dollars.
Hint: Consider the case of n=3 players -- what
information do players 2 and 3 (i.e., the first two people to make
guesses) share? How can player 3 use that shared information to
convey useful information to both players 1 and 2?
Solution: Strategy for player j: count the number of
visible red hats, then add to that the number of "red" guesses made by
earlier players (that is, players n down to j+1). If
that sum is odd, guess "red", if even, guess "blue". Note that, when
stated in this way, it is the same for everyone all the way from the
first guess to the last.
Put another way, player n, the first player to guess, takes the
XOR of all the hats 1 through n-1 (with red being 1 and blue
being 0), and each subsequent player recovers their own color by doing
an XOR of all the colors they see and all the colors they've heard.
Please do NOT post solutions in the comments below. Thanks.
mail me
|