\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