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

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

\raggedbottom

\input{macros-course}
\iffalse
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\fi
%\newtheorem{fact}{Fact}
\begin{document}

\handout{teamprobs7}{Problems for Recitation 7}{October 23, 1998}

\begin{problems}

\problem


Let $S$ be the set of numbers $7, 77, 777, \ldots$. Prove that there
is an element of $S$ that is divisible by $1997$.



\problem

Show that in any sequence of $n$ integers, there is either an 
increasing subsequence of length $\sqrt{n}$ or a decreasing subsequence
of length $\sqrt{n}$. 
 \begin{enumerate} 
  \item Show that every DAG has a chain of length $> \sqrt{n}$ or an antichain of size $\geq \sqrt{n}$.
  \item Define a DAG based on a given sequence of numbers so that chains
correspond to increasing subsequences and antichains correspond to decreasing
subsequences.
  \item Put the above together to solve the problem.
  \end{enumerate}


\end{problems}
\end{document}
