\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{anyfontsize}
\usepackage[super]{nth}
\usepackage{ulem}
\usepackage{multicol}
\usepackage{phaistos}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage[all,arc]{xy}
\usepackage{url}
\usepackage{mathrsfs}
\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{3: Induction/Recursion II}{Due Tuesday, Week 2, at the start of class.}

Solve \textbf{three} of the following \textbf{six} problems.  As always, prove your claims!

\begin{enumerate}

\item Suppose that we have drawn some straight lines in the plane.  This process divides the plane up into several regions, all separated by lines.  Given any such division of the plane into regions, we define a $k$-\textbf{coloring} of our regions as follows: color in each of our regions, using no more than $k$ different colors, so that if any two regions border each other along a line, they are different colors.  For example, here is a $2$-coloring of a plane split into seven regions:
\begin{center}
\includegraphics[width=2in]{planedecomp.pdf}
\end{center}
Suppose that we have in fact drawn $n$ lines in the plane.  For what values of $k$ can we $k$-color the resulting regions?

\item Let $\frac{p}{q}$ denote an arbitrary positive rational number.  Suppose we have the following two actions that we can perform on $\frac{p}{q}$:
\begin{enumerate}
\item Replace $\frac{p}{q}$ with either $\frac{p}{q} + 1$ or $\frac{p}{q} - 1$.
\item Replace $\frac{p}{q}$ with $\frac{q}{p}$.  (This action can only be done if $\frac{p}{q} \neq 0$.)
\end{enumerate}
Show that no matter what rational number we started with, we can get to any other positive rational number.  For example, here is a sequence of actions that turns $\frac12$ into $\frac{22}{7}$:
\begin{align*}
\frac12 \to \frac21 \to \frac31 \to \frac41 \to \frac51 \to \frac61 \to \frac71 \to \frac17 \to \frac87 \to \frac{15}{7} \to \frac{22}{7}.
\end{align*}

\item Take the first $2n$ positive natural numbers $\{1,2,3, \ldots 2n\}$.  Divide them up into two groups of $n$ numbers each, $\{a_1, a_2, \ldots a_n\}$ and $\{b_1, b_2, b_3, \ldots b_n\}$.  Sort the numbers in the first group so that $a_1 < a_2 < \ldots < a_n$, and the numbers in the right group so that $b_n < b_{n-1} < b_{n-2} < \ldots < b_1$.

Prove that no matter how we've divided up our numbers, the sum
\begin{align*}
\sum_{i=1}^n |a_i-b_i|
\end{align*}
is always the same.

\item Suppose we have drawn $2n$ distinct points in space, no three of which are collinear\footnote{A set of points is called \textbf{collinear} if there is some straight line that we can draw that contains all of those points.}.  Pick out $n^2 + 1$ distinct pairs of our points, and for each such chosen pair draw a line between them.  Here is an example for $n=3$:
\begin{center}
\includegraphics[width=2in]{trianglepts.pdf}
\end{center}
Show that no matter how these pairs are chosen, this process always draws at least one triangle between three of our points:
\begin{center}
\includegraphics[width=2in]{trianglepts2.pdf}
\end{center}
\item Show that any positive integer $k$ can be written in the form 
\begin{align*}
\pm 1^2 \pm 2^2 \pm 3^2 \pm 4^2 \pm \ldots \pm n^2,
\end{align*}
for some positive integer $n$ and appropriate choice of signs above.
\item Suppose that $f: \mathbb{R} \to \mathbb{R}$ is a function such that $f\left( \frac{x_1 + x_2}{2}\right) = \frac{f(x_1) + f(x_2)}{2}$, for any two values $x_1, x_2 \in \mathbb{R}$.

Prove that for any $x_1, \ldots x_n \in \mathbb{R}$, we have
\begin{align*}
f\left( \frac{x_1 + x_2 + \ldots + x_n}{n}\right) = \frac{f(x_1) + f(x_2) + \ldots + f(x_n)}{n}.
\end{align*}
\end{enumerate}





\end{document}