\documentclass[12pt, letterpaper]{article}
\usepackage{fullpage}
\usepackage{graphicx}

\title{TJ USAMO Practice 8 - Pigeonhole}
\author{PDiao05}
\date{December 1, 2005}

\begin{document}

\maketitle

\par Say you have 10 pigeons and only 9 holes.  And say you have this 
incredible need to stuff those pigeons into those holes.  Every single pigeon
must be stuffed into a hole.  In fact, we are playing a game and I win if there
ends up being 2 pigeons in at least one of the holes.  Do I win?  

\par Of course I do!

\par And that was how the Pigeonhole Principle was born. It states that if I 
have $n$ pigeons and $m$ holes with $n > m$, I know that I must stuff at least
one of the holes with two pigeons.

\section{Generalizations}

\par Equally intuitive are some generalizations of this principle:

\begin{itemize}

\item If we have n pigeons and m holes and we stuff the pigeons in the holes, 
then at least one of the holes has at least $\displaymath \lceil \frac{n}{m}
\rceil$ many pigeons in it.

\item ``Continuous pigeonhole" also applies.  It is just as intuitive but is 
also very difficult to make rigorous.  Use it anyways.  It basically says if 
you try to stuff area or volume (fat pigeons), into a smaller area or volume
there must be overlap.  For example, you can't fit two squares of area 100 into
a square of area of 150 without overlap.

\end{itemize}

\section{Practice}

\begin{enumerate}

\item Given an equilateral triangle with side length 1 and 5 points in it, prove
that there must be 2 points that are within a distance of 1/2 of each other.
\item If $a_1, a_2, \cdots, a_n$ are integers, show that some non-empty subset
of them has sum divisible by $n$.
\item (MOSP 2005) In a square grid of 169 points, 53 are marked.  Prove that 
some 4 marked points form a rectangle with sides parallel to the grid lines.
\item (MOSP 2005) There are some circles inside a square with side 1.  Suppose 
that the total circumference of the circles of 10.  Prove that there is a line 
which can cut through 4 of those circles.
\item (Dirichlet) Let $\alpha$ be an irrational number.  Show that there are 
infinitely many rational numbers $\frac{m}{n}$ where $m$ and $n$ are relatively
prime integers, for which $|\alpha - \frac{m}{n}| < \frac{1}{n^2}$.  Then
prove the converse just for fun!
\item (MOSP 2005) Given any $n+2$ distinct numbers from the first $3n$ positive
integers, prove that it is always possible to find two numbers $a$ and $b$ from 
them such that $n < a-b < 2n$.

\end{enumerate}

\end{document}