\problemdata
{induction}
{S00 ps2}
{tournament ranking}

\begin{problem}
% tournaments?

Construct the following rankings for $n$-player tournaments, for any
$n \geq 2$, or show that this is not always possible.

\begin{problemparts}

\problempart Assume that one player, Enrique, wins all his matches, and
another, Ricky, wins all but one of his matches.  Construct a ranking
that is locally fair, and in which Enrique is first and Ricky second.

\solution{
Since Enrique beat everyone and Ricky beat everyone but one
  person, it follows that Ricky lost to Enrique.  Now, consider all
  the other players in the tournament.  As seen in class, they can be
  ordered in a locally-fair ranking.  It follows that a locally-fair
  ranking for all the players is the ranking with Enrique first, Ricky
  second, and the remaining players ranked based on a locally-fair
  ranking.  We know that Enrique beat Ricky, that Ricky beat the
  player ranked third since he beat everyone but Enrique, and that the
  remaining players are ranked in a locally-fair fashion.
}

\problempart Assume that there are no sets of 3 players, A, B, and C, such
that A beats B, B beats C, and C beats A; that is, $\nexists A, B, C,
[(A \text{ beats } B) \wedge (B \text{ beats } C) \wedge (C \text{
  beats } A)]$.  Construct a ranking that is extremely fair, in the
sense that any player X that beats another player Y appears higher
than Y in the rankings.
\solution{
 \mbox{} \\
  \begin{theorem*}
    In any tournament with no 3-player cycles, a locally-fair ranking
    is extremely fair.
  \end{theorem*}
  \begin{proof}
    First, consider the case when there is only one or two players.
    In the case of one player, the ranking is trivial.  In the case of
    two players, an extremely fair ranking can be constructed by
    placing the winner first and the loser second.  Now consider a
    tournament of at least 3 players, in which there are no 3-player
    cycles.  In class we have shown that if a tournament has a cycle,
    then the tournament has a 3-player cycle.  Thus, the
    contrapositive is also true; that is, if a tournament has no
    3-player cycle, then the tournament has no cycles.  

    Consider a locally-fair ranking of a tournament with no 3-player
    cycles.  We show that the locally-fair ranking is extremely fair
    by contradiction.  Assume that the locally-fair ranking is not
    extremely fair.  Since the ranking is not extremely fair, there
    exist players $X$ and $Y$ such that $X$ appears higher in the
    ranking than $Y$ even though $Y$ beat $X$, \ie $\cdots X
    \rightarrow \cdots \rightarrow Y \cdots$ and $Y \rightarrow X$.
    It follows that the tournament graph contains the cycle $X
    \rightarrow \cdots \rightarrow Y \rightarrow X$.  Since it
    contains a cycle, it must also contain a 3-player cycle.  This
    contradicts the fact that the tournament has no 3-player cycles.
    It follows that our assumption that the ranking is not extremely
    fair is false.
  \end{proof}
}

\end{problemparts}
\end{problem}




