\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{multicol}
\usepackage{hhline}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}


\homework{8: Ramsey Theory}{Due Tuesday, Week 9, at the start of class}
In class, we mentioned that finding $R(3,3)$ can be thought of as a game:
\begin{itemize}
\item There are two players, Red and Blue.  Their gameboard consists of some number $n$ of points drawn on a plane.  Players alternate turns, and Red starts first. 
\item On a given player's turn, they must connect two points that do not have a line drawn between them yet, with a line of their given color.
\item The game ends when a monochromatic triangle is drawn on the board, in which case that player loses.
\end{itemize}
We proved in class that this game always ends with one player losing (i.e.\ no draws are possible) when $n \geq 6$ because $R(3,3) = 6$.  
\begin{enumerate}
\item Suppose you play the game above on a gameboard with just \textbf{five} points.  Prove that with optimal play from both players\footnote{To illustrate this idea:\ tic-tac-toe is another example of such a game, where with both players playing optimally they can always force a draw.}, this game will always end in a draw. 
\item Assuming that both players play optimally, which player always wins: red or blue?  (Warning: hard!) 
\end{enumerate}
\end{document}