\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{6: Topology}{Due Tuesday, week 8 at the start of class}



This week is like some of the earlier weeks!  To get credit for this problem, just work on it; i.e. think about it, write down ideas, and otherwise spend a hour or two trying to figure out what's going on.  Assignments that show effort (i.e. $>1/2$ page of work and writing, coherent thoughts, good questions for me) will get credit.  

\begin{enumerate}
\item You're now a civil architect!  As such, you're responsible for helping people hook up their houses to the utility network.

At the moment, you have a bit of a problem.  You have three houses $A, B, C$ that have been built in an geologically active area, where lots of small micro-earthquakes happen.  You want to hook up these three houses to the gas, water, and electric utilities; however, due to the risk of earthquakes, you want to do this in a way where none of the lines carrying these utilities have to cross (because if they did, then a small earthquake could cause your lines to cross and cause explosions/doom/etc.)  Can you do this?

In other words: can you connect each of $A, B, C$ to the utilities $G, W, E$ so that the resulting graph is planar?

\item Take a square piece of paper.  If you glue opposite edges as described below, you can turn this square into a \textbf{torus}, i.e. the doughnut shape below:
\begin{center}
\includegraphics[width=4in]{math1c_2012_wk1_torus.pdf}
\end{center}
Can you glue the opposite sides of a hexagon in some clever way to get a torus?  Can you glue together the sides of an octagon to get a ``two-hole dougnhut,'' that is a torus with two holes?  

\end{enumerate}




\end{document}







\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.