\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{5: Invariants}{Due Tuesday, Week 3, at the start of class.}

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

The theme for these problems: on your last set, you looked at the idea of finding \textbf{extremal} elements --- i.e. smallest elements, or biggest elements --- to help you solve a problem.  On this set, every problem can be solved by finding some notion of an \textbf{invariant}: that is, some quantity that \textbf{does not change} for your elements under specific operations.  

To give a quick example, consider the following operation.  Given any natural number $n$, write $n$ in decimal, and sum its digits together to get some new number $n'$.  For example, $8721$ becomes $8+7+2+1 = 18$ under this operation.  By repeating this operation, is it possible for $n = \overbrace{999\ldots 9}^{\textrm{a lot of 9's}}$ to ever get to $1$?

Well: notice that the sum of these digits never changes when considered mod $9$!  This is because for any $k$, $10^k \equiv 1 \mod 9$; therefore, under mod $9$, we cannot tell the difference between $8 \cdot 1000 + 7 \cdot 100 + 2 \cdot 10 + 1$ and $8 \cdot 1 + 7 \cdot 1 + 2 \cdot 1+ 1$.  In this sense, the quantity $n$ mod 9 is an invariant for the number $n$ under our ``sum up all of $n$'s digits'' operation!  Using this invariant, we can see that it is impossible for $\overbrace{999\ldots 9}^{\textrm{a lot of 9's}} \equiv 0 \mod 9$ to ever become $1 \equiv 1 \mod 9$ via this operation.

\begin{enumerate}
\item[0.] Solve any un-signed-up-for problems from HW\#4!
\item You've caught a leprechaun!  He has 753 magical gold coins on him, and offers to play the following game with you:
\begin{enumerate}
\item At the start, all of his gold coins are in one single heap.
\item You can repeatedly perform the following operation: from any heap that contains at least three gold coins, you can remove exactly one gold coin and divide the remaining coins in that heap into two separate heaps.  (These heaps do not have to be the same size, but both of them do need to be nonempty.)
\item You win if at any point, you can make it so that every heap on the table contains exactly three gold coins!  In this case the leprechaun lets you have all of the gold coins.
\item You lose if you cannot win: in this case the leprechaun turns you into a newt.
\end{enumerate}
Should you play this game?
\item Suppose that you're a careless librarian.  Initially, you started with $n$ distinct books all sorted by alphabetical order.  However, when you've returned books over the last year, you've occasionally switched the order of adjacent books in your collection; in other words, you occasionally took out two adjacent books $b,c$ and returned them in the order $c,b$.  Suppose that you've made an odd number of these errors over time.  Is it possible that your errors somehow canceled out: in other words, that you've returned to your initial ordering?  Or can you prove that no matter in what way you've switched pairs of books, you cannot have gotten back to your original ordering?
\item In the city of Gotham, there are many super-powered people.  Suppose that any given super-powered person has at most three distinct \textbf{arch-rivals}, who they cannot bear to work with; suppose furthermore that being arch-rivals is a symmetric relationship (if I am your arch-rival, you are my arch-rival) and also an antireflexive relationship (no-one is their own arch-rival.)

Show that no matter how these rivalries are assigned, it is possible to split up all of our super-powered people into precisely two groups, so that within any group no person has more than one rival.
\item Take any sequence $(a_1, a_2, \ldots a_n)$ of positive integers.  If there are two indices $j < k$ such that $a_j \neq 1$ and $a_j$ does not divide $a_k$, simultaneously perform the following operations:
\begin{itemize}
\item Replace $a_j$ with $gcd(a_j, a_k)$.
\item Replace $a_k$ with $lcm(a_j, a_k)$.
\end{itemize}
Repeat this process as many times as it is possible.  Show that this cannot continue forever; in other words, that eventually our sequence will get to a point where we cannot perform the above process.

(To give an example: suppose we start with $(3,5,9)$.  Our first move could be to choose $a_1, a_2$ and replace them with 1 and 15, respectively; we now have the sequence $(1, 15, 9)$.  From here, we could pick $a_2, a_3$ and replace them with $3, 45$ respectively; we now have the sequence $(1, 3, 45)$, and we cannot perform any more moves.)

\item Suppose that you're trying to model the spread of a given disease through a city.  Model your city as a $12 \times 12$ grid of squares, and suppose that at time $t=0$ there are $11$ infected squares.  To simulate our disease over time, we say that a square is infected at time $n+1$ if and only if it was either infected at time $n$, or at least two of its neighbors were infected at time $n$.

Is it possible that our entire city will become infected?  Or is it impossible for our disease to spread everywhere?

\item Suppose we have an arbitarily large chessboard.  For two positive integers $p, q$, define a $\{p,q\}$-\textbf{powered knight} as an object that on each turn, must move $p$ squares along some axis in either the positive or negative direction, and $q$ squares along the other axis in either the positive or negative direction.  To give an example, a $\{1,3\}$ knight starting at the square $(0,0)$ will be at one of the eight cells $(1,3), (1,-3), (-1,3), (-1,-3),$$(3,1),$ $(3,-1),$ $(-3,1), (-3,-1)$ after its first move.

Can our generalized knight make it back to the origin after an odd number of moves?  Why or why not?
\end{enumerate}





\end{document}