1. ## Hat problem

N players play a game: each player wears a hat that's either red or blue. Each player can see all the other N-1 players' hats but can not see his own hat. The game rule forbids any form of signaling between players during the game. But before the game (before they are put on hats), players can discuss and thus adopt some form of strategy. When the game begins, all players are required to report the color of his own hat simultaneously.

This is just the old hat color game, but now I ask a different question:

Suppose each player has 1/2 independent probability to be put on a red hat. What is the strategy that maximizes the expected number of people who report correctly?

2. ## Re: Hat problem

i am possibly misunderstanding your post, but:

if there is no signalling and all hats are independent of other hats, then no player can get any information about his or her hat and no strategy will do any better than chance.

Are you sure you dont mean to ask about the version of the game where players report one after another, instead of simultaneously? in that case previous calls can contain information and there is a well known solution:

Spoiler:

Hats on a death row!! One of my favorites puzzles! - Brain Teasers Forum - Page 4

if hats are randomly allocated, the first guy will die with probability 0.5 and all the rest will survive.

3. ## Re: Hat problem

Originally Posted by SpringFan25
i am possibly misunderstanding your post, but:

if there is no signalling and all hats are independent of other hats, then no player can get any information about his or her hat and no strategy will do any better than chance.

Are you sure you dont mean to ask about the version of the game where players report one after another, instead of simultaneously? in that case previous calls can contain information and there is a well known solution:

Spoiler:

Hats on a death row!! One of my favorites puzzles! - Brain Teasers Forum - Page 4

if hats are randomly allocated, the first guy will die with probability 0.5 and all the rest will survive.

Yeah you are right. I just realised that my question is trivial. But there's also a well known strategy for this simultaneous game, which guarantees at least N/2 people report correctly in any scenario. You probably know it, too.

Still the simultaneous case, but now suppose there are M different hat colors (M<N). What's the maximum number of people we can guarantee to report correctly in any case? How should we code the colors? Any idea?

4. ## Re: Hat problem

But there's also a well known strategy for this simultaneous game, which guarantees at least N/2 people report correctly in any scenario. You probably know it, too.
I dont know that one. How can you do this if everyone has to report simultaneously?

5. ## Re: Hat problem

Originally Posted by SpringFan25
I dont know that one. How can you do this if everyone has to report simultaneously?
Let's consider N=2k, each player is given a number, say 1,2,3,...,2k. The strategy works like this: player 2i report the hat color of player 2i-1, player 2i-1 report the opposite color of player 2i, for i=1,2,3,...k.

(If N=2k-1, this strategy guarantees k-1 correct report.)

for M=2, better strategy can't be achieved, as discussed here: http://www.mathhelpforum.com/math-he...lem-93518.html