\problemdata                                                             
        {Three players } % latex-friendly label for the prob.
        {game-theoryish problem} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 10, 5} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Consider a game in which three players work as a team. For each player, a red
hat or a blue hat is chosen randomly, each with probability 1/2. Each player
can see the other two players' hats, but not his own. No communication of any
kind is allowed among the players (except for agreeing on strategy, before
the hats are chosen).

The game proceeds with each player making a move simultaneously. The move
consists of either guessing the player's own hat color, or refusing to guess.
The team wins if at least one player guesses, and all guesses are correct;
otherwise the team loses.

\begin{problemparts}
\problempart
Design the best strategy you can for the players, where the quality of
a strategy is measured by the probability that the team wins, and find
this probability for the strategy you design.

\solution{
The strategy is the same for all players: if the two hats a player can
see are the same color, he guesses that his hat is the other color.
If they're different colors, he doesn't guess. 

To see how well the strategy works, consider the eight
possible hat assignments for players 1, 2, and 3. Of these, two (RRR
and BBB) have all hats the same color. In this case (which occurs with
probability 2/8=1/4), the strategy fails. The other six possibilities
(BBR, BRB, BRR, RBB, RBR, RRB) all have two hats of the same color and
one of the other color. In this case exactly one player (the one with
the one hat of the other color) will see two hats of the same color,
and this player guesses correctly, so the strategy succeeds. This case
occurs with probability 6/8=3/4, and is the only case where success
occurs, so the probability of success is 3/4.
}
\problempart
Show that no better strategy is possible.

\solution{
Assume for contradiction that there's a strategy with success
probability $>3/4$. A strategy can be viewed as a function from the
set of 8 hat assignments (ordered triples of colors) to the set of
responses by the 3 players (ordered triples of elements of \{red,
blue,none\}). 

Denote by $r$ the number of hat assignments which map
to sets of responses such that at least one guess is included and all
guesses are correct (i.e. hat assignments for which the strategy
works).
 Denote by $w$ the number of hat assignments which
map to sets of responses having no guess or some wrong guess
(i.e. hat assignments for which the strategy fails). By
assumption $r>3w$. 

Now denote by $g_r$ the total number of guesses over all hat
assignments for which the strategy works, and denote by $g_w$ the
total number of guesses over all hat assignments for which the
strategy fails. Since $r>3w$, $g_r>3w$ (at least one right guess per
successful hat assignment). But $g_w\le 3w$ (at most 3 guesses per
wrong hat assignment since there are 3 players). Thus $g_r>g_w$.

We can show that $g_r=g_w$ and get a contradiction by counting the
total number of guesses. The way to do it is to add up the guesses in 
pairs---any guess made by a player $A$ for a given hat assignment $H$ will
also be made by $A$ for the hat assignment obtained by taking $H$ and
choosing the other color for $A$, and will be wrong in one case and
right in the other. Thus $g_r=g_w$, contradicting $g_r>g_w$.
}
\end{problemparts}
\end{problem}
                                 