\documentstyle[12pt,twoside,amstex]{article}

\addtolength{\topmargin}{-1in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\raggedbottom

\input{macros-course}

\newtheorem{fact}{Fact}
\newtheorem{method}{Method}
%\newcommand{\mod}{ \mbox { mod }}

\begin{document}

\handout{recprobs2}{Problems for Recitation 2}{February 13, 1998}

\begin{enumerate}

\item %From F97 PS2 Problem 10, much revised:

An $n$-player tournament, consists of some set of $n\geq 2$ elements
called {\em players}, and, for every two distinct players, a specification
that one of the players beats the other.  That is, player $p_1$ beats
player $p_2$ iff $p_2$ does not beat $p_1$, for all players $p_1 \neq
p_2$, and no player beats him/herself.

A sequence of players $p_1,p_2, \ldots, p_k$ (for some $k \leq n$), 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$-{\em cycle}.

(a) Prove that in every tournament, either there is a ``champion'' player
that beats every other player, or there is a 3-cycle.

(b) 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.

\item
The well-matched strings of left and right parentheses, {\em WMP}'s
for short, are defined inductively as follows:
\begin{itemize}

\item The string of length two consisting of a left parenthesis followed
by a right parenthesis, namely, {\tt ()}, is a WMP.

\item If $W_1W_2\dots W_k$ is a sequence of $k\geq 1$ WMP's, then $\mbox{\tt
(}W_1W_2\dots W_k\mbox{\tt )}$ is a WMP.

\end{itemize}

The {\em count} of a string of one or more parentheses is defined as
follows:
\begin{itemize}
\item $\mbox{count}(\mbox{\tt)}) = -1$,
\item $\mbox{count}(\mbox{\tt(}) = 1$,
\item of $s$ is a string of parentheses and $p$ is a single parenthesis,
then  $\mbox{count}(sp) = \mbox{count}(s) + \mbox{count}(p)$.
\end{itemize}

A string, $Z$, of one or more parentheses is a {\em well-counting} string
of parentheses, a {\em WCP} for short, iff $\mbox{count}(Z) = 0$ and
$\mbox{count}(X)> 0$ for any proper prefix, $X$, of $Z$.  ($X$ is a {\em prefix}
of $Z$ means that $Z = XY$ for some string $Y$.  $X$ is a {\em proper}
prefix if it is a prefix of $Z$ and its length is positive and strictly
less than the length of $Z$.)

(a) Prove that every WMP is a WCP.

(b) Conversely, prove that every WCP is a WMP.

\end{enumerate}

\end{document}


