\documentclass{article}
\input{preamble.tex}
\title{Day 22}
\date{June 22, 2012}
% \def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut \else {\color{blue} #2} \fi }
\newcommand{\df}{\textbf}
\begin{document}
\maketitle
\section{Pigeonhole Principle}
The study of functions between finite sets yields a few interesting results. One that is particular interesting is when we have two sets $A$ and $B$ and if $|A|>|B|$, then there is no injective function from $A$ to $B$. That is, if we are trying to assign things in $A$ to things in $B$, if $A$ is a larger set then we must hit something more than once. This relatively simple idea is called the \df{Pigeonhole Principle}.
Although not particularly interesting or illuminating in itself, bizarely enough this little theorem tends to have fantastic applications.
\subsection{Formal Statement}
\begin{thm}[Pigeonhole Principle]
If we have $n+1$ objects and we place them into $n$ bins then there must be (at least) one bin with (at least) 2 objects in it.
\end{thm}
This principle of intuitive enough to no precisely call for an explicit proof. Any attempt at writing such a proof will eventually leave you shaking your head, wondering what it is exactly that you are meant to prove.
\subsection{Intuitive Examples}
\begin{eg}
There are at least two, non-bald people in the Pittsburgh metro area with the same number of hairs on their head.
\end{eg}
\begin{eg}
If your Facebook friends list is large enough, there are at least two people with the same birthdate. (How large is `large enough'?)
\end{eg}
\begin{eg}
In this class, there at least two people who have the same height to the nearest inch.
\end{eg}
\begin{eg}
Your family tree has collisions in it; and from more recently than antiquity!
\end{eg}
\subsection{The Form of a Pigeonhole Arguement}
Now that we know the pigeonhole principle, we want to see some of its applications. We begin with a very simple example to illustrate the idea (and potential power).
\begin{thm}
In any list of $n$ numbers, there is either a number divisible by $n$, or two whose difference is.
\end{thm}
\begin{proof}
\Hide{2.5cm}{
Recall that there are $n$ possible remainders when you divide by $n$. If there is a number which is divisible by $n$ on the list, then we are done. Otherwise, the $n$ numbers are all in $n-1$ different categories (the congruence classes mod $n$). Therefore, by the pigeonhole principle there are two numbers in the same congruence class mod $n$, $x$ and $y$. As proved, $x-y$ is then divisible by $n$.
}
\end{proof}
This leads to a codification of the general idea of a proof by the pigeonhole principle. The difficulty lies in setting up the pigeonholes. They should have the property that
\begin{enumerate}
\item They span the universe of objects; that is every object will be put in a holes.
\item They are all disjoint; an objects is never placed in two holes.
\item There aren't many; in particular, less than the number of object (or maybe much less if you want to iterate).
\item If you knew multiple things shared a pigeonhole, you would get a desire property.
\end{enumerate}
In the above, we set up the pigeonholes (which were non-zero congruence classes mod $n$). These span the universe (ie. every integer is in one of them), they are disjoint, and there are $n-1$ of them, whereas we have $n$ objects. Finally, we knew that the difference of two numbers in the same class is divisible by $n$.
\begin{eg}
For any choice of $10$ numbers in $[19]$, there are two that add up to $19$.
\begin{soln*}
\Hide{1in}{
We partition our universe $[19]$ into the following: $\s{1,18},\s{2,17},\s{3,16},\ldots,\s{9,10}$. There are $9$ parts of the partitions, and notice if two things are chosen that lie in the same partition then there sum is $19$. As we are chosing $10$ numbers, and there are only $9$ parts of the partition, there must be two numbers chosen that lie in the same part. They add to $19$.
}
\end{soln*}
\end{eg}
It is almost always the case that the challenge of these problems is that it is difficult to determine what the pigeonholes are.
\begin{eg}
For any choice of $10$ numbers from $[100]$ we can break them up into two, nonempty subsets who have the same sum.
\begin{soln*}
\Hide{2in}{
Here it is not immediately clear what the pigeonholes are. But, we can easily bound the sum of $\leq10$ numbers from this list at $1000$. This is of course larger than we could achieve, but we hope it is a good enough. Therefore, there are at most $1000$ possible sums achievable by a subset of $10$ numbers chosen from this list.
Now, fix the 10 numbers in questions. We want to show that there are two disjoint subsets of them whose sum is the same. Well, how many subsets are there? There are $2^{10}$ possible subsets, and as we are requiring that they be nonempty there is $1023$ possible which are nonempty. Thus there are $1023$ possible ways to break up these 10 elements into two, nonempty parts.
For each of these subsets, we calculate their sum (we ``put them in a pigeonhole according to their sum''). There are, as stated above, at most $1000$ possible sums, as there is $1023$ subsets, we know there are two distinct subsets with the same sum.
Call these subsets $S_1$ and $S_2$. Unfortuantely, these need not be disjoint. But, we can fix this, as clearly $S_1\minus (S_1\cap S_2)$ is disjoint from $S_2\minus (S_1\cap S_2)$, and they have the same sum.
}
\end{soln*}
\end{eg}
\begin{rmk}
Iterating the pigeonhole principle gives us the following fact: if we have $n$ objects and $k$ bins, then there is (at least) one bin with (at least) $\left\lceil\frac{n}{k}\right\rceil$ many objects in it.
\end{rmk}
\begin{eg}
There is a 50 mile stretch of land owned by the King, who gives permission to 12 Lords claim 10 miles lengths of land. Prove that there will be a point that is contested between $3$ Lords.
\begin{soln*}
\Hide{1.25in}{
Imagine the stretch of land as a line, and each Lord places a marker on the line, then captures the next $10$ miles of that line. Now, we can divide this line into $5$ 10 mile segments. By the pigeonhole principle, there must be $\left\lceil\frac{12}{5}\right\rceil = 3$ Lords whose starting marker is in the same fragment. The endpoint of the fragment is contested.
}
\end{soln*}
\end{eg}
\newpage
\subsection{Worksheet}
\begin{eg}
If $5$ points are placed in the unit square, then there are two points that are within $\frac{1}{\sqrt{2}}$ distance of each other. This is not true with only $4$ points, and is not true for $5$ points for a distance $<\frac{1}{\sqrt{2}}$. (This shows the result is ``best possible'').
\end{eg}
\begin{soln*}
\Hide{1in}{
Divide a square into 4 quadrants. By the pigeonhole principle, two of the points are in the given quadrant. The farthest two points can be in the same quadrant is the length of the diagonal of the square, which is $\frac{1}{\sqrt{2}}$. Therefore, those two points are close.
By chosing $4$ points, the corners of the square, we see none are closer than unit $1$ apart. We see by adding a point to the center of the square, none of the points are closer than $\frac{1}{\sqrt{2}}$.
}
\end{soln*}
\begin{eg}
Any way that one chooses $n+1$ numbers from $[2n]$ there are two numbers $l,k$ chosen where $l\mid k$. This result is best possible; that is, there is a way to choose $n$ numbers that doesn't have this property.
\end{eg}
\begin{soln*}
\Hide{1in}{
Partition the numbers in $[2n]$ by the equivalence relation $a\sim b$ if and only if the odd part of $a$ and $b$ are the same. These equivalence classes are given by an odd number, and contain that odd number and all the multiples by a power of $2$. As there are $n$ odds less than $2n$, there are $n$ equivalence classes. As we are choosing $n+1$ numbers, two of the numbers are in the same equivalence class, and thus one is a multiple of the other.
}
\end{soln*}
\begin{eg}
Take any sequence of $n$ numbers. There is a consecutive subsequence of these numbers whose sum is divisible by $n$. That is the say, for any sequence $a_1, a_2, \ldots, a_n$ there is a $k$ and $l$ such that $a_k + a_{k+1} + a_{k+2} + \cdots + a_{k+l}$ is divisible by $n$
\end{eg}
\begin{soln*}
\Hide{1in}{
The idea is that we look at the initial sums
\begin{align*}
&a_1 \\
&a_1 + a_2 \\
&\vdots \\
&a_1 + a_2 + \cdots + a_n
\end{align*}
These are all numbers, and there is $n$ of them. Mod $n$ there are only $n$ possible remainders. If one of these things has remainder 0, we are done. Otherwise, there are two of them with the same remainder. Subracting them, we get something divisble by $n$ and a sequence as specified.
}
\end{soln*}
\begin{eg}
For any natural number $n$, there is a number $N$ composed whose decimal representation is composed only of $0$'s and $1$'s which is divisible by $n$.
\end{eg}
\begin{soln*}
\Hide{1in}{
We look at decimals composed of strings of $1$'s. The first $n$ of them, say.
\begin{align*}
&1\\
&11\\
&111\\
&\vdots\\
&\underbrace{111\cdots 1}_{n-\mbox{many}}
\end{align*}
If one of these has remainder $0$ when divided by $n$, we are done. Otherwise, two have the same remainder. Subtracting the larger minus the smaller, we get a sequence of $1$'s followed by $0$'s which is divisible by $n$
}
\end{soln*}
\end{document}