\section{Tournaments}

A pure math example, interesting and slightly complicated (ordinary
and strong) inductive proofs. \\

A new Internet game company is conducting a chess tournament on the Internet.\\
Round robin, not elimination. \\
That is, everyone plays everyone exactly once. \\
Can represent the results nicely by arrows, e.g.:\\
\\
A beats B, C, D \\
B beats D \\
C beats B \\
D beats C \\
\\
See Figure \ref{tournamentintro}.
\begin{figure}[h]
\begin{center}
\scalebox{0.4}{\rotatebox{270}{\includegraphics{figures/tournamentintro}}}
\end{center}
\caption{A digraph representing the outcome of a tournament}\label{tournamentintro}
\end{figure}


Structure called a ``digraph''.  We'll study them carefully soon.\\
\\
Now, the gaming company wants to use this information to make some
decisions, e.g., award first prize, rank everyone. \\
It wants to do this in such a way that its customers don't complain
about the rankings being unfair. \\
\\
There are some problems with doing this.

\subsection{Cycles}

Problem: The tournament graph can contain cycles. \\
Example: Above, B beats D beats C beats B. \\
\\
If there's a cycle, then any ranking method is a least a little
problematic:  someone who beat someone else would be ranked lower. \\
\\
Of course, the company has no power to avoid cycles in play
results. \\
The gaming company might hope that ``most of the time'', when there is
a cycle, it's very big (so the people involved aren't likely to
discover this). \\
However, tournaments have an unfortunate property: 
\begin{theorem}
Any tournament that contains any cycle, contains a cycle of length $3$
($3$-cycle).
\end{theorem}

That is, three players, e.g., B, C, D, above, have an ``inconsistent''
set of results. \\
\\
This can be proved by ordinary induction, where $P(n)$ is the
predicate ``Any tournament that contains an $n$-cycle contains a
$3$-cycle.''
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 3 [P(n)]$ \\
1. (Base) $P(3)$ 
\> \> \> \> \> Trivial by assumption. \\
2. (Inductive step)  $\forall n \geq 3 [P(n) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 3$ \\
\> 2. Assume $P(n)$ \\
\> 3. $P(n+1)$ \\
\> \> 1. Fix $T$, a tournament, and $p_1 \rightarrow p_2 \rightarrow \ldots
\rightarrow p_{n+1} \rightarrow p_1$, an $n+1$-cycle in $T$. \\
\> \> 2. $T$ contains a $3$-cycle. 
      \> \> \> ??? \\
\> \> 3. QED
      \> \> \> Implication, UG \\
\> 4. QED
   \> \> \> \> Implication, UG \\
3. QED
\end{tabbing}
How can we find a $3$-cycle in $T$? \\
Example:

\begin{figure}[h]
\begin{center}
\scalebox{0.32}{\includegraphics{figures/tournament}}
\end{center}
\caption{A tournament graph containing a 5-cycle}
\end{figure}


 %[[[Draw 5-cycle]]]. \\
To get a $3$-cycle, notice that $p_1$ and $p_3$ have an arrow, one way
or the other.  \\
If from $p_3$ to $p_1$, then $p_1,p_2,p_3$ form a cycle.\\
If the other way, then can reduce the size of the cycle to omit $p_2$.
Then use induction on the smaller cycle. \\
This generalizes: 
\begin{tabbing}\\
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $T$ contains a $3$-cycle. \\
\> \> \> 1. If $p_3 \rightarrow p_1$ then $T$ contains a $3$-cycle. 
      \> \> Use $p_1 \rightarrow p_2 \rightarrow p_3 \rightarrow p_1$. \\
\> \> \> 2. If $p_1 \rightarrow p_3$ then $T$ contains a $3$-cycle. \\
\> \> \> \> 1. Assume $p_1 \rightarrow p_3$. \\
\> \> \> \> 2. $T$ contains an $n$-cycle. 
            \> Use $p_1 \rightarrow p_3 \rightarrow p_4 \rightarrow p_{n+1} \rightarrow p_1$. \\
\> \> \> \> 3. $T$ contains a $3$-cycle.
            \> By inductive hypothesis (2.2) \\
\> \> \> 3. QED
         \> \> Cases
\end{tabbing}
A detail to be careful about here: 
This argument depends on the fact that the arrow we add between $p_1$ and
$p_3$ is not already part of the original cycle. \\
That's true because we know that the original cycle had length $n+1$,
which is at least $4$. 

\subsection{``Nice'' rankings}

The gaming company decides that, although they cannot avoid inconsistent
orders, they would at least like to make the ranking ``nice'',
by which they mean that if one player $p$ is ranked {\em immediately
ahead\/} of another player $q$, then $p$ must have beaten $q$. \\
(They might want to tell each player who the players were that are
ranked immediately above and below him, and don't want someone to
complain that the guy ranked above him is someone he beat.) \\
They are happy to discover: 
\begin{theorem}
Any tournament has a nice ranking.
\end{theorem}

\noindent
Example:  Above:  Can use ranking $A, D, C, B$.

Prove by strong induction, where $P(n)$ says ``any $n$-player
tournament has a nice ranking''. \\
The strategy is to ``split'' the players into those that beat and
those that lose to a particular player $x$. \\
Rank those two subsets separately, by using the inductive
hypothesis.\\
(Subtournaments) \\
Then put the rankings together. 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 1 [P(n)]$ \\
1. (Base) $P(1)$ 
\> \> \> \> \> Obvious---just one player to be ranked. \\
2. (Inductive step)
$\forall n \geq 1 [(\forall i, 1 \leq i \leq n (P(i))) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 1$ \\
\> 2. Assume $\forall i, 1 \leq i \leq n [P(i)]$. \\
\> 3. $P(n+1)$ \\
\> \> 1. Fix any $n+1$-player tournament $T$. \\
\> \> 2. $T$ has a nice ranking. \\
\> \> \> 1. Choose $x$ to be any player, $B$ the set of players that
beat $x$, and $L$ the \\
\> \> \> \> set of players that lose to $x$. \\
\> \> \> 2. $B$ has a nice ranking. 
         \> \> Inductive assumption (2.2). \\
\> \> \> 3. $L$ has a nice ranking. 
         \> \> Inductive assumption (2.2). \\
\> \> \> 4. Define a ranking $R$ of all the players by: $B$ ranking, then $x$, then $L$ ranking. \\
\> \> \> 5. $R$ is a nice ranking for $T$. \\
\> \> \> 6. QED 
         \> \> EG \\
\> \> 3. QED 
      \> \> \> UG \\
\> 4. QED
   \> \> \> \> Implication, UG \\
3. QED                        
\> \> \> \> \> Strong induction 
\end{tabbing}

\forstudents{
\subsubsection{Nice rankings and number of wins}

For a while, the customers are happy with just nice rankings. \\
But then a game comes up where just ``niceness'' doesn't work out so well: \\
\\
Example: (See Figure \ref{outcome1}) \\
A beats B \\
B beats C \\
C beats A,D \\
D beats A,B,E \\
E beats A,B,C 


%[[[Diagram]]] 
\begin{figure}[h]
\begin{center}
\scalebox{0.4}{\includegraphics{figures/whobeatswhom}}
\end{center}
\caption{Outcome of the game}\label{outcome1}
\end{figure}



Here, A,B,C,D,E is a nice ranking. \\
However, it's in the reverse order according to number of wins. \\
Bad. \\
Now it occurs to the company that it would be nice if the rankings could
also be consistent with number of wins. \\
It turns out this is not possible (in combination with ``niceness''). 
%
%Example: 6 players \\
%A beats C,D,E,F (4 wins) \\
%B beats A,E,F (3 wins) \\
%C beats B,F (2 wins) \\
%D beats C,B (2 wins) \\
%E beats C,D (2 wins) \\
%F beats D,E (2 wins) \\
%
%(Draw)
%
%Ordering consistently with number of wins would mean $A$ would have to
%be ranked immediately ahead of $B$. \\
%But $B$ beats $A$, violating niceness. \\\
%
So then they decide they will be happy to settle for a nice ranking in
which the highest ranked player has the largest number of wins (can be
tied). \\
This would rule out the bad example above. \\
\\
Turns out this is possible: \\
In fact, in the event of a tie, the company has the option of choosing
which best player is ranked first: \\
\\
Define $P(n)$: For any $n$-player tournament $T$ and any $z$ that has
the largest number of wins in $T$, there exists a nice ranking
with $z$ ranked first. 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 1 [P(n)]$ 
\end{tabbing}
This can be proved by induction, but the inductive step is more
complicated than in the previous proof. \\
\\
First proof attempt: \\
Try a proof like the previous one, this time splitting on some $x$
that loses to $z$. \\
Now split all-but-$x$ into $B$ and $L$ as before, based on their
records with respect to $x$. \\
We know that $z$ is in $B$, because it beats $x$. \\
Now try to use the inductive hypothesis to rank $B$ while keeping $z$
first, and to rank $L$. \\
Then combine as before. \\
\\
Sounds plausible---but wrong: \\
Applying the inductive hypothesis requires that $z$ have the best
won-lost record in the ``subtournament'' involving just the $B$
elements. \\
But it might not: \\
\\
Example: (See Figure \ref{outcome2})\\
Players z, y, x, and a lot of p's \\
z and y beat x \\
x beats all of the p's \\
y beats z \\
z beats all the p's \\
All the p's beat y \\
Doesn't matter what happens among the p's. 
\begin{figure}[h]
\begin{center}
\scalebox{0.45}{\includegraphics{figures/outcome2}}
\end{center}
\caption{Outcome of the game}\label{outcome2}
\end{figure}

%[[[diagram]]] 

$z$ has the best record overall, but in the two-player subtournament consisting
of guys that beat $x$, $z$ is worse than $y$. \\
\\
Try again: \\
It turns out that a correct proof can be given using ordinary (not
strong) induction: \\
Recall $P(n)$: For any $n$-player tournament $T$ and any $z$ that has
the largest number of wins in $T$, there exists a nice ranking
with $z$ ranked first. 
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
Prove: $\forall n \geq 1 (P(n))$ \\
1. (Base) $P(1)$ 
\> \> \> \> \> Only one possibility. \\
2. (Inductive step) $\forall n \geq 1 [P(n) \Rightarrow P(n+1)]$ \\
\> 1. Fix $n \geq 1$. \\
\> 2. Assume $P(n)$. \\
\> 3. $P(n+1)$. \\
\> \> 1. Fix $T$, an $n+1$-player tournament, and $z$, a player with the most wins. \\
\> \> 2. $\exists$ a nice ranking of $T$ with $z$ first. 
      \> \> \> ??? \\
\> \> 3. QED 
      \> \> \> UG \\
\> 4. QED   
   \> \> \> \> Implication, UG \\
3. QED                        
\> \> \> \> \> Induction 
\end{tabbing}
The key step will break down into cases, based on whether or not $z$
lost any matches.  \\
The case where $z$ won everything is easy; the other case is tricky:
Here's the easy case:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> 2. $\exists$ a nice ranking of $T$ with $z$ first. \\
\> \> \> 1. If $z$ is undefeated in $T$ then $\exists$ a nice
ranking of $T$ with $z$ first. \\
\> \> \> \> 1. Assume $z$ is undefeated in $T$. \\
\> \> \> \> 2. Choose $R$ to be a nice ranking of all-but-$z$. \\
\> \> \> \> \> Previous theorem says this exists, EI \\
\> \> \> \> 3. $z$ then $R$ is a nice ranking of $T$. \\
\> \> \> \> 4. $\exists$ a nice ranking of $T$ with $z$ first. \\
\> \> \> \> \> EG \\
\> \> \> \> 5. QED 
            \> Implication \\
\> \> \> 2. If $z$ is defeated by someone then $\exists$ a nice
ranking of $T$ with $z$ first. \\
\> \> \> \> \> ??? \\
\> \> \> 3. QED 
         \> \> Cases
\end{tabbing}

And the tricky case:
\begin{tabbing}
XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
\> \> \> 2. If $z$ is defeated by someone then $\exists$ a nice
ranking of $T$ with $z$ first. \\
\> \> \> \> 1. Assume $z$ is defeated by someone. \\
\> \> \> \> 2. Choose $x$ to be someone who defeated $z$. \\
\> \> \> \> 3. $z$ has the best record in the subtournament involving all-but-$x$.\\
\> \> \> \> \> $z$ had the best record in $T$, \\
\> \> \> \> \> no wins are removed. \\
\> \> \> \> 4. $\exists$ ranking of subtournament having $z$ first. \\
\> \> \> \> \> Inductive hypothesis, $z$ has best record. \\
\> \> \> \> 5. Choose $R$ to be a ranking of all-but-$x$ having $z$ first. \\
\> \> \> \> \> EI \\
\> \> \> \> 6. In $T$, $x$ is defeated by someone. 
            \> $z$ was defeated, and $x$'s record in $T$ can't \\
\> \> \> \> \> be better than $z$'s. \\
\> \> \> \> 7. Define ranking $S$ to be $R$, with $x$ inserted right after the lowest-ranked player \\
\> \> \> \> that beats $x$. \\
\> \> \> \> 8. $S$ is a nice ranking of $T$. \\
\> \> \> \> \> $R$ is nice, $x$ is beaten by the player ranked \\
\> \> \> \> \> just above it and beats all ranked below it. \\
\> \> \> \> 9. $z$ is first in $S$. 
            \> $z$ is first in $R$, and $x$ is not inserted \\
\> \> \> \> \> at the top. \\
\> \> \> \> 10. $\exists$ a nice ranking of $T$ with $z$ first. \\
\> \> \> \> \> $S$ works, EG \\
\> \> \> \> QED 
            \> Implication \\
\end{tabbing}
}