\begin{problem}
Tennis tournaments consists of a series of matches between two players.
Usually the objective is to determine a single best player among a set of
players.  The organizers of the 6.042 tournament want to do more: they
want to find a linear ranking of all the players.  To avoid controversy,
they want to avoid the awkward situation of having is a sequence of
players each of whom beats the next player in the sequence, and the last
player beats the first.  So the organizers will keep a running record of
who beat whom during the tournament and never allow simultaneous matches
whose outcomes could lead to an awkward situation.

Knowledge of binary relations can help the organizers in arranging the
tournament.  Namely, at any stage of the tournament, the organizers have a
record of who lost which completed matches.  Mathematically, we can say
that there is a binary relation, $L$, on players where $p\, L\, q$ means
that player $p$ lost a match to player $q$, and there are no awkward
situations means that the positive length path relation, $L^+$, of $L$ is
a strict partial order.  Which of the partial order properties listed
below correspond to the following properties of a stage of the tournament:

Partial Order properties:
\begin{enumerate}
\item incomparable
\item comparable
\item maximal
\item maximum
\item minimal
\item minimum
\item chain
\item total order
\item topological sort
\item empty partial order
\item antichain
\item maximal antichain
\item irreflexive
\item reflexive
\end{enumerate}

\bparts
\ppart An unbeaten player is a \brule{1in} element of the partial order.
\solution{maximal}

\ppart A player who has lost every match he was in is a \brule{1in}
element of the partial order $L^+$.  \solution{miximal}

\ppart A player who is sure to rank first at the end of the tournament is
a \brule{1in} element of $L^+$.  \solution{maximum}

\ppart Two players who should not be matched in the next stage of the
tournament are \brule{1in} elements of $L^+$.

\ppart A group of players whose rankings relative to each other is
completely known is a(n) \brule{1in}.  \solution{chain; ``total order'' is
also ok.}

\ppart An even number of players who could be paired up in an arbitrary
way to play the next set of matches is a(n) \brule{1in}.
\solution{antichain}

\ppart The fact that no player loses to himself correspond to $L^+$ being
a(n) \brule{1in} partial order.  \solution{irreflexive}

\ppart The final ranking at the end of the tournament must be a(n)
\brule{1in} of $L^+$.
\solution{topological sort}

\eparts

For the following parts, assume there are 256 players in the tournament.

\bparts

\ppart What is the smallest number of matches that could possibly have been
played in a completed tournament? \solution{255}

\ppart Assuming each match takes an hour and matches are scheduled to be
played simultaneously on the hour, what is the smallest number of hours the
tournament could take? \solution{8}
\end{problem}

\begin{problem}
Relate each of the following relational expressions to the relation
property it describes from the list below.

properties: transitive, reflexive, irreflexive, symmetric, antisymmetric,
asymmetric,

expressions:
$R^2 \subseteq R$ \solution{transitive},\\
$R = R^+$ \solution{transitive},\\
$I_A \subseteq R$ \solution{reflexive},\\
$I_A \intersect R = \emptyset$ \solution{irreflexive},\\
$R^{-1} \subseteq R$ \solution{symmetric},\\
$R^{-1} \intersect R \subseteq I_A $ \solution{antisymmetric}.
\end{problem}
