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

%\raggedbottom

\input{macros-course}

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

\begin{document}

\recn{7}{3/20}{March 18, 1998 (edited 3/21)}

\section{The Pigeonhole Principle}

We showed in lecture that for finite sets, $\card{A} \leq \card{B}$ iff
there is an injection from $A$ into $B$.  The contrapositive of this fact
is

\begin{corollary} [The Pigeonhole Principle]
\label{cor:pigeon}
If there are more pigeons than pigeonholes, then there must be at least
two pigeons in one hole.

Formally, let $A$ and $B$ be finite sets.  If $|A| > |B|$ and $f: A
\mapsto B$, then there exist distinct elements $a$ and $a'$ in $A$ such
that $f(a) = f(a')$.
\end{corollary}

As a trivial application of the Pigeonhole Principle, suppose that
there are three people in a room.  The pigeonhole principle implies
that two have the same gender.  In this case, the ``pigeons'' are the
three people and the ``pigeonholes'' are the two possible genders,
male and female.  Since there are more pigeons than holes, two pigeons
must be in the same pigeonhole; that is, two people must have the same
gender.

The pigeonhole principle seems too obvious to be really useful, but
the next two examples show how it gives short proofs of results that
are difficult to obtain by other means.

A problem on an old final exam was to prove the following claim:

\begin{claim}
In every set of 1000 integers, there are two integers $x$ and $y$ such
that $573 \mid (x-y)$.
\end{claim}

At first glance, this looks very hard!  Those 1000 numbers could be
anything!  Since there are no less than 1000 integer-valued variables
here, even our old standby, induction, seems hopeless.  Surprisingly,
however, there is a short proof using the Pigeonhole Principle.

To apply the Pigeonhole Principle, we must identify two things:
pigeons and holes.  Furthermore, to prove anything with the Pigeonhole
Principle, we must have more pigeons than holes.  Since there are only
two numbers mentioned in this problem, a natural thing to try is 1000
pigeons and 573 holes.

Under this interpretation, a pigeon is an integer, but what is a hole?
Ideally, the existence of two pigeons and in the same hole should be
equivalent to the existence of two numbers $x$ and $y$ such that $573
\mid (x-y)$.  This suggests numbering the holes $0, 1, \ldots 572$ and
putting in hole $n$ all integers congruent to $n$ modulo 573.  Now we
can construct a proof:

\begin{proof}
Let $S$ be a set of 1000 integers.  Let $M = \{ 0, 1, \ldots 572
\}$.  Let $f: S \mapsto M$ be the function defined by $f(n) = n \bmod
573$.  Since $|S| > |M|$, Corollary~\ref{cor:pigeon} implies that there
exist distinct elements $x$ and $y$ in $S$ such that $f(x) = f(y)$.
This means $(x \bmod 573) = (y \bmod 573)$ and so $573 \mid (x-y)$.
\end{proof}

Really there was nothing special about the numbers 1000 and 573 other
than the fact that $1000 > 573$.  We could have made a stronger claim:
if $n > m$, then in every set of $n$ integers, there are two integers
$x$ and $y$ such that $m \mid (x-y)$.

\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.

\textbf{Example:} 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 $200,000,000/1000,000 = 200$ pigeons. That
is there are at least 200 Americans with exactly the same number of hairs
on their heads.

\textbf{Example:} Consider the following problem: we are to number the
squares of a chessboard from 1 to 64.  Is it possible to do this so that
the difference between the numbers of any pair of adjacent squares
(horizontally, vertically or diagonally) is no more than 8 ?

The answer is NO.  Consider the square numbered 1 and the square numbered
64. We know that no matter where they are placed, there is a path of
length at most 7 between them (i.e., in at most 7 hops to adjacent
squares, we can go from the 1-square to the 64-square).  To go from 1 to
64, there is a difference of 63 to be covered in 7 hops.  Let us think of
this difference as 63 pigeons and they have to each be placed in one of 7
holes.  The holes represent which hop the step is taken in.  Now by the
strong PP there must be a hole with at least 63/7 = 9 pigeons.  This means
that there must be a hop which covers a difference of 9 or greater.  That
is there are a pair of adjacent squares that differ by at least 9.


\subsection{Pigeonhole Principle Example: Weighing Balls}

In the first tutorial you may have seen the following problem
(illustrating reasoning by cases).  There are 3 balls of which 2
have the same weight and one has a different weight.  With two weighings
on a balance scale, you must identify the odd ball and determine whether
it is heavier or lighter than the rest.  (A balance scale has a left pan
and a right pan.  In a weighing you put some balls in each pan.  The scale
then reveals whether the left pan is heavier, the right pan is heavier, or
the two are equal.)

The problem is solvable using a strategy algorithm represented by a
ternary tree.  Each internal node in the tree represents a weighing such
as, ``put balls 1, 3 on one side and 2, 4 on the other side''.  Each leaf
node represents a result such as, ``the 3rd ball is heavier than the
rest''.  A run of the algorithm corresponds to a path from the root to a
leaf.  At each internal node, we perform the weighing associated with the
node.  Based on the result -- ``leaning left'', ``leaning right'' or
``balanced'' we descend to one of the three children.  When we reach a
leaf, we output the indicated result.

       (labels of balls in left pan, labels of balls in right pan)

\begin{verbatim}
                                  (1,2)
                                   /|\
                                  L = R
                                 /  |  \
                                /   |   \
                          (1,3)   (2,3)   (2,3)
                         /|\       /|\       /|\
                        L = R     L = R     L = R
                       /  |  \   /  |  \   /  |  \  
                      1H  2L 1L

\end{verbatim}
``1H'' means ball 1 is heavy, ``2L'' means ball 2 is light, etc.

\textbf{Class exercise}: Fill in remaining leaves.

Suppose that we wanted to solve the same problem with more balls, but
still with only 2 weighings.  If there are 5 balls, then we can apply
pigeonholing to prove that no solution exists.  (Of course we could do a
simple case analysis here too, but case analysis gets elaborate if not
prohibitive when there are a lot of balls, while pigeonholing can give
simple bounds.)

\begin{claim}
The weighing problem with 5 balls cannot be solved with 2 weighings.
The weighing problem with 14 balls cannot be solved with 3 weighings.
\end{claim}

\begin{proof}
The pigeons are the possible situations.  Since any one of balls could be
the different weight one, and it could be either heavier or lighter than
the rest.  With 5 balls there are 10 pigeons, with 14 balls there are 28
pigeons.  The holes are the 9 leaves of the depth-2 ternary tree used to
represent the weighing strategy for the 5 ball case, or the 27 leaves of
the depth-3 tree in the 14 ball case.  Since there are more pigeons than
holes, the Pigeonhole Principle implies that some hole must have two
pigeons; that is, some leaf is not associated with a unique situation.
Therefore, for every weighing strategy, there is some pair of situations
that the strategy cannot distinguish.  In at least one of these
situations, the strategy must give the wrong answer.
\end{proof}

In general, if there are $n$ balls, we can compute a lower bound on
the number of weighings necessary.  In this case, there are $2n$
possible situations.  If there are $w$ weighings, then every strategy
can be represented by a ternary tree with $3^w$ leaves.  For a correct
weighing strategy to exist, there must be as many leaves as
situations.  That is, we must have $3 ^ w \geq 2n$ or, equivalently,
$W \geq \log_3 2n$.

\section{Dilworth}
We proved in an earlier recitation:
\begin{theorem}
If $t$ is the length of the longest chain in a poset $(A, \preceq)$
then $A$ can be partitioned into $t$ antichains.
\end{theorem}

Review: {\bf chain}: all elements comparable (total order); {\bf
antichain}: all elements incomparable.

We can use this along with Pigeonholing to prove a famous result about
posets:

\begin{theorem}
(Dilworth) If $t$ is the length of the longest chain in a poset with $n$
elements, then the poset has an antichain of size $\geq n/t$.
\end{theorem}

\begin{proof}
By previous result, the $n$ elements can be partitioned into
$t$ antichains.  The pigeons are the $n$ elements.  The holes are the $t$
antichains.  By Strong Pigeonholing, there must be $\geq n/t$
pigeons in some hole.
\end{proof}

Posets arise in all sorts of contexts, and when they do Dilworth's theorem
can have interesting implications.  As you will show in your second Team
Problem.

\section{Team Problems}

\begin{problems}

\problem
\bparts

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

\ppart Suppose $n > 1$ and we place checkers on exactly $n+1$ squares of
the $n \times n$ checkerboard.  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

\textbf{Solution}:

(a) There are $n(n-1)$ possible distinct ordered pairs of numbers
$0,\dots,n-1$, and so $n(n-1)/2$ sets of exactly two such numbers, and
$n(n-1)/2 + n = n(n+1)/2$ sets of one or two numbers.

(b) The distance between checkers at distinct positions $(x_1,y_1)$ and
$(x_2,y_2)$ is uniquely determined by the set of two numbers
$\set{\abs{x_1 - x_2}, \abs{y_1 - y_2}}$.  The values of these differences
can be $0,\dots,n-1$ except that both can't be zero since the positions
are different.  These are the holes.  So there are $n(n+1)/2 - 1$ holes.

Each set of two checkers is a pigeon.  There are $(n+1)n/2$ pigeons by
reasoning as in (a).  A pigeon gets assigned to a hole which is the
difference of the $x$ and $y$ coordinates of the checker positions.  Since
there is one more pigeon than hole, there must be two pigeons in the same
hole.  That means the $x$ and $y$ coordinate differences, and hence the
distance, between the two pigeons is the same.

\problem
\textbf{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}$.

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

\medskip
\textbf{Solution}:

(a) There are two total orders involved here: numerical $<$ and ``comes
before'' in the sequence.  Let's abbreviate ``comes before'' as
\textbf{ cb }.  The relation $\preceq$ is the intersection of these orders.
It's easy to verify that the intersection of two partial orders is always
a partial order, so $\preceq$ is a partial order.

(b) Increasing chains under $\preceq$ are the same as increasing
subsequence, because by definition, $a_1 \prec a_2 \prec \cdots \prec a_t$
iff both
\[a_1 < a_2 < \cdots < a_t,\]
and also
\[a_1 \mbox{\textbf{ cb }} a_2 \mbox{\textbf{ cb }} \cdots \mbox{\textbf{ cb }} a_t.\]

On the other hand, antichains are decreasing subsequences.  To prove this,
note:
\begin{lemma}\label{prec}
If $a,b$ are $\preceq$-incomparable and $a > b$, then $a
\mbox{\textbf{ cb }} b$.
\end{lemma}

\begin{proof}
If $b$ comes before $a$, then since $b < a$, we would also have $b \prec
a$, contradicting the assumption that $a$ and $b$ are incomparable.
\end{proof}

\begin{lemma}
If 
\[a_1 > a_2 > \dots > \cdots a_t,\]
and $a_1, a_2, \cdots, a_t$ are $\preceq$-incomparable,
then $a_1, a_2, \cdots a_t$ is a decreasing subsequence.
\end{lemma}

\begin{proof}
Since $a_i > a_{i+1}$, Lemma~\ref{prec} implies that $a_i$ comes before
$a_{i+1}$, that is, $a_1, a_2, \cdots a_t$ is a subsequence.
\end{proof}

So given an antichain, arrange the elements in decreasing order and this
will be a decreasing subsequence.

(c) If there is no increasing subsequence of length $> \sqrt{n}$, then the
$\preceq$ partial order does not have a chain of length $> \sqrt{n}$.  By
Dilworth's Theorem, it must have an antichain of length at least
$n/\sqrt{n} = \sqrt{n}$.  But the elements of an antichain determine a
decreasing subsequence.

\end{problems}
\end{document}
