\documentclass[12pt]{article}
\usepackage{comment}
\usepackage{bm}
\usepackage{amsmath}
\usepackage{amssymb}

\begin{document}

\centerline{\bf Homework 10 MORALLY Due Apr 25 at 9:00AM}
\newcommand{\Prob}{{\rm Pr}}
\newcommand{\MOD}{{\rm MOD}}
\newcommand{\PRIMES}{{\rm PRIMES}}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}

\newcommand{\NCU}{{\rm NCU}}
\newcommand{\NCUZ}{{\rm NCUZ}}


\centerline{\bf WARNING: THIS HW IS FOUR PAGES LONG!!!!!!!!!!!!!!!!!}



\begin{enumerate}

\item 
(0 points but please DO IT)
What is your name?

\item
(30 points)
Fill in $XXX(n)$ and PROVE the following USING the technique of partitioning the 
square by superimposing a $n\times n$ grid on it
(so into $n^2$ squares).

{\it For every set of $n^2+1$ points in the unit square there exists
two points that are $\le XXX(n)$ apart.}



\vfill

\centerline{\bf GOTO NEXT PAGE} 

\newpage


\item 
(35 points) 
Fill in $YYY(n)$ and PROVE the following USING the technique of partitioning the 
square by superimposing a $4\times 4$ grid on it, and getting lots of points in that
region, and then superimposing a $4\times 4$ grid on that region, etc. 

{\it For every set of $2^n+1$ points in the unit square there exists
two points that are $\le YYY(n)$ apart (you can assume $n$ is odd or even as you see fit).}



\vfill

\centerline{\bf GOTO NEXT PAGE} 

\newpage
\item 
(30 points) 
Fill in $ZZZ$ and PROVE the following.

{\it For any 3-coloring of the $4\times ZZZ$ grid there is a monochromatic rectangle.}

\vfill

\centerline{\bf GOTO NEXT PAGE} 

\newpage

\item 
(Extra Credit)
We know from class that 

{\it if there are 5 points in the unit square then there are 2 that are
$\le \frac{\sqrt{2}}{2}$ apart.}

Let $d_5=\frac{\sqrt{2}}{2}$ apart.  
\begin{itemize}
\item
Find a number $d_6<d_5$ such that 

{\it if there are 6 points in the unit square then there are 2 that are
$\le d_6$ apart.}

\item 
Find a number $d_7<d_6$ such that 

{\it if there are 7 points in the unit square then there are 2 that are
$\le d_7$ apart.}

\item
Find a number $d_8<d_7$ such that 

{\it if there are 8 points in the unit square then there are 2 that are
$\le d_8$ apart.}




\end{itemize}


\end{enumerate}
\end{document}