        \problemdata       % Takes 5 *mandatory* arguments
        {tourn-induction}             % latex-friendly label for the prob.
        {induction}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 PS2-8, F97 PS2-10 (much revised)} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
(* difficult) %From F97 PS2 Problem 10, much revised by ARM

An $n$-player tournament, consists of some set of $n\geq 2$
\emph{players}, and, for every two distinct players, a specification that
one of the players beats the other.  That is, player $p$ beats player $q$
iff $q$ does not beat $p$, for all players $p \neq q$.

A sequence of distinct players $p_1,p_2, \ldots, p_k$, such that player
$p_i$ beats player $p_{i+1}$ for $1 \leq i < k$ is called a {\em ranking}
of these players.  If also player $p_k$ beats player $p_1$, the ranking is
called a $k$-\emph{cycle}.

\begin{problemparts}

\problempart Prove by induction that in every tournament, either there is a
``champion'' player that beats every other player, or there is a 3-cycle.

\solution{The induction hypothesis $P(n)$, is
``In an $n$-player tournament, either there is a player that
beats every other player, or there is a 3-cycle.''

\textbf{Base case} $n=2$: By definition of a 2-player tournament, one of the
players beats the only other player and therefore is the champion.

\textbf{Inductive step}:
Assume that $P(n)$ is true in order to show that $P(n+1)$ is true.

Consider an $n+1$-player tournament.  If there is a champion, we are done.
So we may assume that every player is beaten by some other player.  Now
remove any player, say player $p$, and treat the remaining $n$ players as an
$n$-player tournament.  There are two cases:

1) Every player in the $n$-player tournament is beaten by some other
player in the tournament.

2) There is some champion in the $n$-player tournament who beats every
other player in the $n$-player tournament.

In case (1), we have by induction hypothesis a 3-cycle of players in the
$n$-player tournament.  Since a 3-cycle in the $n$-player tournament will
also be a 3-cycle in the full $n+1$-player tournament, we are OK in this
case.

In case (2), there is some ``champion'', $q$, in the $n$-player
tournament.  Since everybody in the ($n+1$)-player tournament is beaten by
somebody, $q$ must be beaten by a player not in the $n$-player tournament,
that is, $p$ beats $q$.  For the same reason, there is some
player $r$ that beats $p$.  Since $r$ is in the $n$-player tournament, $r$
is beaten by the champion $q$.  So we have found a 3-cycle $p,q,r$.
}

\problempart
A {\em consistent ranking} is a sequence $p_1,p_2, \ldots, p_n$ of all
$n$ players in the tournament such that $p_i$ beats $p_j$ iff $i < j$, for
$1 \leq i,j \leq n$.  Conclude that a tournament has no consistent ranking
iff some subset of three of its players has no consistent ranking.

\solution{By definition of tournament, the restriction of the
tournament to any subset of two or more of its players is also a
(sub)tournament.  Also any consistent ranking of a tournament remains
consistent when restricted to a subset of players.  So if some subset of
three players has no consistent ranking, then the whole tournament
can't have a consistent ranking either.

So we have only to prove the converse implication: if every three players
have a consistent ranking, then the tournament as a whole has one.
The proof is by induction on $n$.

{\bf Base case $n=2$:} Every two player tournament obviously has a
consistent ranking.

{\bf Inductive step:} Suppose $n\ge2$ and there is a consistent ranking of
any tournament of $n$ players whose three-player subsets have consistent
rankings.  Now consider any $n+1$ player tournament whose three-player
subsets have consistent rankings.

This tournament cannot have a 3-cycle, because there is no consistent
ranking for the players in the 3-cycle.  Hence, by the previous part, the
tournament has a champion.  The $n$-player tournament obtained by ignoring
the champion also has no 3-cycles, so by induction it has a consistent
ranking.  Then this ranking of $n$-nonchampions followed by the champion
at then end is a consistent ranking of the whole tournament of $n+1$
players.
}
\end{problemparts}


\end{problem}