\problemdata                                                             
        {Round Robin Tournaments} % latex-friendly label for the prob.
        {Probabilistic Method} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 12, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           

A round robin tournament of $n$ contestants is one in which each of the
$\binom{n}{2}$
pairs of contestants play each other exactly once, with the outcome of any play
being that one of the contestants wins and the other loses. For a fixed integer
$k$, $k < n$, a question of interest is whether it is possible that the
tournament outcome is such that for every set of $k$ players there is a player
who beat each player of this set. Show that if:
\[ \binom{n}{k} \left[1 - \left(\frac{1}{2}\right)^k \right]^{n-k} < 1 \]
then such an outcome is possible.

\begin{problemparts}

\problempart

Start by numbering the  sets of $k$ contestants. How many such sets are there?

\solution{
\[
\binom{n}{k}
\]
}

\problempart

Let $B_i$ be the event that no contestant beat all the $k$ contestants in set
$i$. Compute $\Pr(B_i)$. (Note that you must choose probabilities for each match
in order to compute this).

\solution{
Suppose that the results of the game are independent and that each game is
equally likely to be won by either contestant. This is an arbitrary choice, but
it is easy to work with (and any probability will suffice to prove existance).
The probability that a person inside group $i$ beats everyone in $i$ is 
clearly $0$. The probability that a person outside group $i$ beats everyone
in $i$ is $\left(\frac{1}{2}\right)^k$, so the probability the person they did not
beat everyone in $i$ is $1 - \left(\frac{1}{2}\right)^k$. There are $n-k$ people
outside of group $i$. Thus, $B_i$ has probability 
\[
\left[1 - \left(\frac{1}{2}\right)^k \right]^{n-k}
\]
}

\problempart

Give an upper bound on $\Pr(\cup B_i)$.


\solution{
Then use Boole's inequality to bound: $\Pr(\cup B_i) \leq \sum \Pr(B_i)$.
In other words, $\Pr(\cup B_i)$ can be no greater than if all of the
$B_i$ are disjoint. (Overlap will merely reduce the total probability of
the union). Since the expression for $B_i$ does not depend on $i$ -- the
probability is the same for each $k$-sized group $i$ -- the sum of all of
the $B_i$ is simply 
\[
\binom{n}{k} \left[1 - \left(\frac{1}{2}\right)^k \right]^{n-k}
\]
}

\problempart

Explain why this result can be used to prove the existence of the desired
tournament outcome.

\solution{
Probabilistic proof. If the overall probability of $\cup B_i$ is less 
than 1 then there must be an occurrence that is not in $\cup B_i$. It
does not matter that we chose the probabilities arbitrarily; the fact that
there is \emph{any} probaility at all left over means some outcome that we
had not accounted for is possible.

\medskip 
For interest, some numbers that work are:

$k = 1, n = 3; k = 2, n = 21;  k = 3, n = 33; k = 4, n = 46;$ \\
$k = 5, n = 59; k = 6, n = 72; k = 7, n = 85; k = 8, n = 98$
}

\end{problemparts}
\end{problem}
                                 

