\documentclass[12pt,ifthen]{article}
\usepackage{amsmath,amssymb}
%\usepackage{html}
%\usepackage{url}
\usepackage{hyperref}
\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}}

\begin{document}

\centerline{\bf Homework 6, Morally Due Tue April 14, 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.

\begin{enumerate}

\item
(0 points)
What is your name?  Write it clearly.


\item
(50 points)
In the March 31 recording I gave three proofs of the following theorem:

{\bf Theorem:} For all $k$ there exists $n$ such that, for any $n$ points in the plane no three colinear,
there exists $k$ points that form a convex $k$-gon.
One proof used 5-ary Ramsey.

One proof used 3-ary Ramsey and the coloring

$COL(x,y,z)$ is RED if the number of points inside the x-y-z triangle is RED is even, BLUE if its odd.

One proof used 3-ary Ramsey and the following coloring: let $p_1,\ldots,p_n$ be the points (the ordering
does not correspond to anything geometric, but we need SOME way to order the points).

$COL(p_i,p_j,p_k)$ with $i<j<k$ is RED if $p_i,p_j,p_k$ is clockwise and BLUE if its counterclockwise.

I did not finish that proof. So the problem is to finish part of the proof: Finish the case
where the homog set is RED. You may draw pictures and reason from them.

\item
(50 points) Read the notes with link {\it One Probe Search Algorithms}. Write up a description of
the cell probe algorithm that takes only one probe for when $U=2n-2$.


\end{enumerate}

\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: