\documentclass[12pt,ifthen]{article} \usepackage{amsmath,amssymb} %\usepackage{html} %\usepackage{url} \usepackage{hyperref} \newcommand{\spec}{\rm spec} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\into}{{\rightarrow}} \newcommand{\st}{\mathrel{:}} \newcommand{\finv}{f^{-1}} \newcommand{\COL}{\mathrm{COL}} \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{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\degg}{{\rm deg}} \begin{document} \centerline{\bf Homework 9, Morally Due Tue May 5, 2020, 3:30PM} COURSE WEBSITE: \url{http://www.cs.umd.edu/~gasarch/858/S18.html} \newif{\ifshowsoln} \showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks. \centerline{\bf THIS HW IS ONE PAGES LONG!!!!!!!!!!!!} \bigskip \begin{enumerate} \item (0 points) What is your name? Write it clearly. \item (50 points) In this problem you may assume that, for all $c$, there exists $N=N(c)$ such that for all $c$-colorings of $[N]\times[N]$ there exists a monochromatic square. Show that there exists $M$ such that, for all 2-colorings of $[M]\times[M]$, there exists five points that are the same color of the following form: $(x,y)$ $(x+d,y)$ $(x,y+d)$ $(x+d,y+d)$ $(x+2d,y+d)$ (This is called a {\it Little Dipper}.) You can (and should) prove this by making drawings and pointing to stuff. \item (50 points) Assume that you know that, for all $c$, $W(100,c)$ exists. Prove that $W(101,2)$ exists. You can draw diagrams; however, your proof should be completely rigorous. \end{enumerate} \end{document}