\problemdata                                                             
        {loaded dice} % latex-friendly label for the prob.
        {intransitive dice} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 11, 5} % 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}
Last time, we proved that if $p = (\sqrt{5} - 1)/2 = 0.618\ldots$\footnote{Note that $p$ is a root of $x^2 + x - 1$}, then the dice have the property that on any roll of dice A and B, the
probability that A beats B is $p$, 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}.


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.

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{

\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{problem}
                                 