\problemdata     
{S01-PS6-3}           
{Pigeonhole Principle}              
{S99-PS7, S01-PS6} 		
{S01 Karger}


\begin{problem}

Let $D$ be the diamond-shaped region of the
real plane consisting of all points $(x, y)$ such that $|x| + |y| \leq
1$.
Prove that among every set of 5 points in $D$, there must exist two
distinct points that are at most unit distance apart.  \hint  Consider
the diagram below.

\graphicspath{{/toc/a/class/6.042/spring02/freshRepository/figures/}}


\bigskip
\centerline{\resizebox{2.0in}{!}{\includegraphics{ps6-diamond}}}
\bigskip

\solution{The diagram for the preceding problem part shows that the
set $D$ can be partitioned into four smaller diamonds.  By the
pigeonhole principle, at least two of the five points must be
contained in the same small diamond.  These two points are distance at
most one apart.

(Note that boundary points can be assigned to smaller diamonds
arbitrarily.)
}

\end{problem}