\documentclass[10pt]{article}
\usepackage[Mickael]{ammaths}
\begin{document}
\en
\nocouleur
\module{The Tower of Hanoi}{3}{18}{2 periods}
\prereq{Introduction to proof by induction.}
\object{\begin{itemize}
\item Understand the usefulness of induction in algorithms.
\end{itemize}}
\mater{\begin{itemize}
\item Cardboard towers of Hanoi.
\item Beamer.
\item Wooden tower of Hanoi.
\end{itemize}}
\modpart{Find the shortest number of moves for $n\in\{2,3,4\}$.}{25 mins}
Studest work in pairs or groups of three to find a way to move the tower to its destination. Number of moves are
compared.
\modpart{Study the movements}{30 mins}
Answer to the following questions :
\begin{itemize}
\item Where to move the first disk ?
\item Is it possible to describe a simple algorithm solving the puzzle ?
\item What is the lowest possible number of moves for a $n$ disks tower?
\end{itemize}
\modpart{The formula for $n$ disks}{35 mins}
Prove the general formula for the number of moves for the $n$ disks tower. Then, use it to answer the question from the
legend : when will the end of the world take place ?
\modpart{Graph representation}{20 mins}
The graph of all possible moves is shown for $n=2$, $n=3$ and $n=4$. Relation with the Sierpinski triangle is noted.
\pagebreak
\moddocdis{The Tower of Hanoi}{3}{18}{Lesson}
The puzzle was invented by the French mathematician \emph{Édouard Lucas} in 1883. It's based on a Vietnamese or Indian
legend about a temple which contained a large room with three time-worn posts in it surrounded by 64 golden disks. The
priests of Brahma, acting out the command of an ancient prophecy, have been moving these disks from the first post to
the third, in accordance with the following rules :
\begin{itemize}
\item Only one disk may be moved at a time.
\item Each move consists of taking the upper disk from one of the posts and sliding it onto another post, on top of the
other disks that may already be present on that post.
\item No disk may be placed on top of a smaller disk.
\end{itemize}
According to the legend, when the last move of the puzzle is completed, the world will end. It is not clear whether
Lucas invented this legend or was inspired by it.
\sectionblack{Simple solution to the puzzle}
The following procedure yields the lowest possible number of moves to move any number of disks from the first post to the third.
\begin{quote}
If the number of disks is odd, start by moving the smallest disk to the destination post. If the number of disks is
even, start by moving the smallest disk to the intermediary post.
Then, alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move
it in the same direction (either to the left or to the right, according to your first move, but be consistent). If there
is no tower in the chosen direction, move it to the opposite end. When the turn is to move the non-smallest piece, there
is only one legal move.
\end{quote}
\sectionblack{The lowest number of moves}
\theo{}{The lowest number of moves necessary to move a $n$ disks tower is $2^n-1$.}
\proo{Let's prove this result by induction.\\
\begin{description}
\item[Basis :]First, consider the $1$-disk situation. Then, the lowest number of moves is obviously $1=2^1-1$, so the property is true.
\item[Inductive step :]Then, suppose that we have proved the lowest number of moves needed to move a $k$ disks tower is
$2^k-$, for a natural number $k$. Let's look at the $k+1$ disks tower. To move it to the destination post, we must first
move the $k$ disks at the top of the tower to the intermediary post, then move the largest disk to the destination post,
then move the $k$ disks tower from the intermediary post to the destination post. According to our induction hypothesis,
the total number of moves for this procedure is
$$(2^k-1)+1+(2^k-1)=2\times 2^k-1=2^{k+1}-1.$$
So the property is true for the $k+1$ disks tower.
\item[Conclusion :] Since both the basis and the inductive step have been proved, it has now been proved by mathematical
induction that the property holds for all natural $n$.
\end{description}}
\sectionblack{The end of the world}
If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest
number of moves, it would take them $2^{64}-1$ seconds or roughly 600 billion years to move the whole tower.
\pagebreak
\moddoc{Cardboard towers of Hanoi}
\begin{multicols}{2}
\begin{center}
\psset{unit=0.6cm}
\begin{pspicture}(0,0)(8,8)
\pspolygon(0,0)(8,0)(8,1)(0,1)
\pspolygon(0.5,1)(7.5,1)(7.5,2)(0.5,2)
\pspolygon(1,2)(7,2)(7,3)(1,3)
\pspolygon(1.5,3)(6.5,3)(6.5,4)(1.5,4)
\pspolygon(2,4)(6,4)(6,5)(2,5)
\pspolygon(2.5,5)(5.5,5)(5.5,6)(2.5,6)
\pspolygon(3,6)(5,6)(5,7)(3,7)
\pspolygon(3.5,7)(4.5,7)(4.5,8)(3.5,8)
\end{pspicture}
\end{center}
\begin{center}
\psset{unit=0.6cm}
\begin{pspicture}(0,0)(8,8)
\pspolygon(0,0)(8,0)(8,1)(0,1)
\pspolygon(0.5,1)(7.5,1)(7.5,2)(0.5,2)
\pspolygon(1,2)(7,2)(7,3)(1,3)
\pspolygon(1.5,3)(6.5,3)(6.5,4)(1.5,4)
\pspolygon(2,4)(6,4)(6,5)(2,5)
\pspolygon(2.5,5)(5.5,5)(5.5,6)(2.5,6)
\pspolygon(3,6)(5,6)(5,7)(3,7)
\pspolygon(3.5,7)(4.5,7)(4.5,8)(3.5,8)
\end{pspicture}
\end{center}
\end{multicols}
\begin{center}
\psset{unit=0.6cm}
\begin{pspicture}(-0.5,-0.5)(28.5,10.5)
\pspolygon[fillstyle=solid,fillcolor=lightgray](0,0)(28,0)(28,1)(0,1)
\pspolygon[fillstyle=solid,fillcolor=lightgray](4.7,1)(4.7,10)(5.3,10)(5.3,1)
\pspolygon[fillstyle=solid,fillcolor=lightgray](12.7,1)(12.7,10)(13.3,10)(13.3,1)
\pspolygon[fillstyle=solid,fillcolor=lightgray](20.7,1)(20.7,10)(21.3,10)(21.3,1)
\pspolygon(-0.5,-0.5)(-0.5,10.5)(28.5,10.5)(28.5,-0.5)
\end{pspicture}
\end{center}
\begin{center}
\psset{unit=0.6cm}
\begin{pspicture}(-0.5,-0.5)(28.5,10.5)
\pspolygon[fillstyle=solid,fillcolor=lightgray](0,0)(28,0)(28,1)(0,1)
\pspolygon[fillstyle=solid,fillcolor=lightgray](4.7,1)(4.7,10)(5.3,10)(5.3,1)
\pspolygon[fillstyle=solid,fillcolor=lightgray](12.7,1)(12.7,10)(13.3,10)(13.3,1)
\pspolygon[fillstyle=solid,fillcolor=lightgray](20.7,1)(20.7,10)(21.3,10)(21.3,1)
\pspolygon(-0.5,-0.5)(-0.5,10.5)(28.5,10.5)(28.5,-0.5)
\end{pspicture}
\end{center}
\end{document}