What color hat am I wearing?
... random thoughts , logic , math
tue 2005-may-10 15:07:22 pdt
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
You can guarantee all but the very first guess. That is, you
can ensure a win of at least n-1 million dollars.
(a hint for how)
Please do NOT post solutions in the comments below. Thanks.