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

%\raggedbottom

\input{macros-course}

\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{recprobs#1}{Problems for Recitation #1 (#2/98)}{#3}
}

\begin{document}

\recn{7}{3/20}{March 18, 1998}

\begin{problems}

\problem Suppose $n > 1$ and we place checkers on exactly $n+1$ squares of
the $n \times n$ checkerboard.

\bparts

\ppart

There are $n^2$ ordered pairs of integers $0,\dots,n-1$, of which all but
$n$ have distinct elements.  How many sets of size one \emph{or} two are
contained in the set of integers $0,\dots,n-1$?

\ppart
Show that some length occurs more than
once as the distance between two different checkered squares.  (More
precisely, there are checkered squares $S1\neq S2$ and $S3\neq S4$ such
that the distance between $S1$ and $S2$ is the same as the distance
between $S3$ and $S4$, but $\set{S1,S2} \neq \set{S3,S4}$.)
\eparts


\problem
\begin{claim}
In any sequence of $n$ different numbers, there is either an increasing
subsequence of length $> \sqrt{n}$ or a decreasing subsequence of length
$\geq \sqrt{n}$.
\end{claim}
For example
\[ 6 4 7 9 1 2 5 3 8\]
has the decreasing sequence
\[6 4 1\]
and the increasing sequence
\[1 2 3 8.\]
That is, it has ``long'' subsequences of both kinds.

Consider some sequence of $n$ numbers.  To prove the claim, say for
numbers $a,b$ in the sequence, that $a \preceq b$ iff either $a = b$, or
else both $a < b$ and also $a$ comes before $b$ in the sequence.

\bparts
\ppart  Verify that $a \preceq b$ is a partial order on the elements of
the sequence.

\ppart What kind of subsequences are chains in this poset? \dots antichains?
Prove it.

\ppart Prove the Claim.
\eparts

\end{problems}
\end{document}
