\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{5: Algorithms}{Due Tuesday, week 6, 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 The Towers of Hanoi is the following puzzle: Start with $3$ rods.  On one rod, place $n$ disks with radii $1, 2, \ldots n$, so that the disk with radius $n$ is on the bottom, the disk with radius $n-1$ is on top of that disk, and so on/so forth.  

The goal of this puzzle is to move all of the disks from one rod to another rod, obeying the following rules:
\begin{itemize}
\item You can move only one disk at a time.
\item Each move consists of taking the top disk off of some rod and placing it on another rod.
\item You cannot place a disk $A$ on top of any disk $B$ with radius smaller than $A$.
\end{itemize}
\begin{center}
\includegraphics[width=2in]{MC2012_wk5blurbs_hanoi.pdf}
\end{center}
\begin{enumerate}
\item How many disk-movements at most does it take you to solve this problem for $n = 1$?  $n=2$?  $n=3$?  $n=4$?
\item Write down an algorithm for solving this problem!  (I.e.\ create step-by-step instructions to solve the Towers of Hanoi.)
\item What is the runtime of your algorithm?  (Measure your runtime in terms of the total number of disks moved.)
\item A story, told by the mathematician \'Edouard Lucas, claimed that there was a monastery where monks were tirelessly solving a instance of the Tower of Hanoi problem made with 64 disks, and that when they finish their game the world will end.  Suppose these monks can make an average of one move per second, and started around 1000BC.  When will they complete their game (approximately?)
\end{enumerate}


\item Great news:\ for your birthday, you got a totally sweet Towers of Hanoi set!

 Bad news:\ in your mathematical joy, when you unwrapped your present you bent the middle peg pretty badly.
\begin{center}
\includegraphics[width=3in]{hanoi2.pdf}
\end{center}
As a result, when you play with your Towers of Hanoi set, you can't really leave pegs on the middle tower for too long.  To help with this, you've came up with a variation on the Towers of Hanoi rules. The normal Towers of Hanoi rules are as follows:
\begin{itemize}
\item Start with $3$ rods $A,B,C$.
\item On rod $A$, place $n$ disks with radii $1, 2, \ldots n$, so that the disk with radius $n$ is on the bottom, the disk with radius $n-1$ is on top of that disk, and so on/so forth.
\item Your goal is to move all of the disks from the far-left rod $A$ to the far-right rod $C$, subject to the following rules:
\begin{itemize}
\item You can move only one disk at a time.
\item Each move consists of taking the top disk off of some rod and placing it on another rod.
\item You cannot place a disk $D_i$  on top of any other disk $D_j$ with radius smaller than $D_i$.
\end{itemize}
\end{itemize}
You've changed the rules above as follows:
\begin{itemize}
\item[--] If you are moving disks from the broken rod $B$, you can move them all as one big stack (instead of one-by-one.)  You still can't place bigger disks on top of smaller disks, but this should hopefully make it so we move disks away from $B$ faster!
\end{itemize}
\begin{enumerate}
\item Let $h_n$ denote the smallest number of moves needed to move all of the disks from $A$ to $C$ in this new game.  (Note: we assume $h_0 = 1$ here for calculational convenience.)  Find a recurrence relation on the $h_n$'s.


\item Use this to find a closed form for $h_n$.  (Hint: it's related to the Fibonacci sequence!)
\end{enumerate}
\end{enumerate}




\end{document}