\documentstyle[12pt]{article}
\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{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}

\begin{document}

{\bf Tutorial 7.}

\date{}

\section{How many trees?}

\section{Strong pigeonholes}

The {\em Strong Pigeonhole Principle}. If $n(r-1)+1$ pigeons are placed
in $n$ holes then there is at least one hole with $r$ or more pigeons in
it.

{\em Proof. }  By contradiction. Assume for the purpose of a contradiction
that there is a way of placing the pigeons in the holes so that all the 
holes have $r-1$ or fewer pigeons. Then the total number of 
pigeons is at most $n(r-1)$. This is a contradiction since we assumed
that there are at least $n(r-1)+1$ pigeons. \qed

An equivalent way of stating the principle is: If $n$ pigeons are 
placed in $r$ holes, then there is at least one hole with $\lceil n/r \rceil$
pigeons in it.

As a simple application, we will prove that there are at least 200 Americans
with {\em exactly} the same number of hairs on their heads. First we estimate
that the number of hairs on any person's head is at most a million. There
are over 200 million Americans. To apply the strong pigeonhole principle,
think of Americans as pigeons, and that there is a hole for each unique
number of possible hairs. That is all Americans with the same number of hairs
go into the same hole. Now by the pigeon hole principle there must
be some hole that gets at least $200000000/1000000 = 200$ pigeons. That is
there are at least 200 Americans with exactly the same number of hairs on
their heads.

To see a more involved application, let us recall the definitions of a chain
and an antichain in a DAG (directed acyclic graph). 

A {\em chain} in a DAG is a sequence of vertices $a_1,a_2,\ldots,a_m$ such
that there is a directed edge from $a_1$ to $a_2$, a directed edge from
$a_2$ to $a_3$,\ldots, and a directed edge from $a_{m-1}$ to $a_m$.

An {\em antichain} in a DAG is a set of vertices $b_1, b_2, \ldots b_m$ 
such that there is no directed path between any pair of distinct vertices
in the set.

Recall also that if the longest chain in a DAG with $n$ vertices 
is of length $t$, then the $n$ vertices can be partitioned into 
$t$ antichains. 

\begin{theorem} (Dilworth) 
For any $t \geq  0$, every DAG with $n$ vertices either has a chain
of length greater than $t$ or an antichain of size at least 
$\lceil n/t \rceil$.
\end{theorem}

{\em Proof. }
By the strong pigeonhole principle. We will prove this for any $t$. 
Consider some $t$. If there is a chain of length $>t$ then we are done.
So assume that the longest chain has length $\leq t$. Then we know the 
$n$ vertices can be partitioned into $t$ antichains. Think of the antichains
as the holes and the vertices as the pigeons. Then there must be some
hole with at least $\lceil n/t \rceil$ pigeons in it. That is there is
an antichain of size at least $\lceil n/t \rceil$. \qed
  
\section{Team Problems}
\begin{enumerate}
\item Let $S$ be the set of numbers $7, 77, 777, \ldots$. Prove that there
is an element of $S$ that is divisible by $1997$.

\item 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}

\item  
A boolean function from the naturals to $\{0,1\}$ is a finite 
piece of code (in your favourite programming language). The code takes 
as input a natural number and outputs $0$ or $1$. Prove that not 
all boolean functions $f$ are computable.
 \begin{enumerate}
  \item What is the cardinality of the set of finite programs ?
  \item What is the cardinality of the set of boolean functions ?
  \item From the above, deduce that there are uncomputable boolean functions.
 \end{enumerate}
\end{enumerate}

\end{document}


