\problemdata                                                             
        {Loaded Dice} % latex-friendly label for the prob.
        {Probability} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 10, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Consider an example of three loaded dice A, B,
C with the properties
\begin{itemize}
\item Die A always comes up 3.
\item Die B is 2 with prob $p$ and 5 otherwise.
\item Die C is 4 with prob $p$ and 1 otherwise.
\end{itemize}
These are claimed to have the property that on any roll of dice A and B, the
probability that A beats B is $p = (\sqrt{5} - 1)/2 = 0.618\ldots$, on a
roll of B and C the probability that B beats C is $p$, and likewise on a
roll of C and A, the probability that C beats A is $p$.  That is, the
``probably beats'' relation on these dice is \emph{intransitive}.

\begin{problemparts}
\problempart Prove the claim. \hint Note that $p$ is a root of $x^2 + x - 1$.

\solution{

\textbf{Solution:}\\
It's clear that A beats B, and C beats A, each with probability $p$.

From the hint we have $1 - p^2 = p$.  Now the probability that B beats C
is
\[
\prob{\text{B rolls to 5}} + \prob{\text{B rolls to 2 and C rolls to 1}}
= (1-p) + p(1-p) = 1 - p^2 = p.
\]

}

\end{problemparts}

Can we increase this probability?  That is, can we construct dice so that
the probability of A beating B, B beating C, C beating A are each, say, at
least 3/4?  The answer is ``No.''  In fact, the probabilities cannot all
exceed 2/3.  More precisely, consider the experiment of rolling all three
dice.  Define $A$ to be the event that A beats B, $B$ the event that B
beats C, and $C$ the event that C beats A.

\begin{problemparts}

\problempart Prove that
\[
\min \set{\prob{A}, \prob{B}, \prob{C}} \leq \frac{2}{3}.
\]
\hint Observe that $\prob{A \intersect B \intersect C} = 0$ and apply
Boole's Inequality to the complement.

\solution{

\textbf{Solution:}\\
\begin{proof}
\[\begin{array}{rcll}
\prob{A \intersect B \intersect C}
    & = & 1 - \prob{\bar{A} \union \bar{B} \union \bar{C}} 
          & \mbox{DeMorgan's Law}\\
    & \geq & 1 - (\prob{\bar{A}}+ \prob{\bar{B}} + \prob{\bar{C}}
                & \mbox{by Boole's Inequality}\\
    & = & \prob{A} + \prob{B} + \prob{C}) - 2 & 
\end{array}\]
But $\prob{A \intersect B \intersect C} = 0$,
since it is impossible that on any single roll, die A is higher than die B,
\emph{and} B is higher than C, {\em and} C is higher than A.
Hence
\[2  \geq  \prob{A} + \prob{B} + \prob{C} \geq 3 \min \set{\prob{A},\prob{B},\prob{C}}\]
and therefore
\[2/3 \geq \min \set{\prob{A}, \prob{B}, \prob{C}}.\]
\end{proof}

% \textbf{Extra Credit Problem}: Show that the 2/3 bound can be improved to $p
% = (\sqrt{5} - 1)/2 = 0.618\ldots$, and that this is the minimum bound. 

}

\end{problemparts}
\end{problem}
                                 