# Edit Create an Image Page: Towers of Hanoi

To create an image page, simply complete the form below and then hit the 'Save Page' button at the bottom of the form. As you complete the form, remember that one of the main goals of the Math Images Project is to provide explanations of the images on our site at various levels, so that everyone can understand some of the math behind the images. Try to complete the form as fully as possible, but remember that other users will have the opportunity to add more information to your image pages in the future. Also, please note that by contributing to the Math Images Project, you agree to comply to the guidelines as stated in our general disclaimer.

As always, thank you for your contributions! --The Math Images Project

If you need help filling out this page, please consult our Help sections: Want to Contribute and Math Resources.

Note: * Indicates a required field.

Please note: When you are filling in the below explanations, you should feel free to use standard wikitext.

 Image Title*: Upload a Math Image Towers of Hanoi is a well known puzzle game publicized in 1883 by Édouard Lucas, a French mathematician. According to legend, priests of the Hindu god Brahma were instructed to move 64 golden disks from one of 3 poles to another, and when they completed it, the world would end.http://www.lawrencehallofscience.org/java/tower/ The standard game begins with 3 poles, one of which (the starting pole) has some natural number, ''k'', disks placed around it in increasing size from top to bottom, while the other poles start out empty. :'''Goal''': Move all ''k'' disks from the starting pole (typically the leftmost) to the specified end pole (typically the rightmost), following these rules: :*Only one disk may be moved at one time. :*Each move consists of moving the top disk of one pole onto the top of another pole. :*Each disk must be placed on a larger disk. The game is solvable and has a shortest solution (fewest moves) for any number of disks. To fully understand the game's legend, one must understand the relationship between the number of disks and the number of moves. As it turns out, this relationship is [[Exponential Growth|exponential]] (see A More Mathematical Section for details). We can see the effects of this exponential relationship in the legend about the priests, who had to move 64 disks from one pole to the other. If they were to move one disk per second, then they would need 18,446,744,073,709,551,615 seconds, or 584.54 billion years, to complete the game. Given that this is about 58.5 times the life span of the Sunhttp://helios.gsfc.nasa.gov/qa_sun.html, the legend probably overestimates the amount of time we have until the world ends (unless we can survive without the Sun and the Earth). ===Play the Game=== You can play the game Towers of Hanoi right here! This applet will help you understand how the game works. {{Hide|1= }} ===Example of Solving the Game=== Solving Towers of Hanoi with 4 disks. {{Hide|1=[[Image:ToH4.gif]]}} ==The Recursive Solution== This game becomes more interesting when we try to figure out the shortest solution for any number of disks. We will first state an algorithm that solves the game, then show that this algorithm is the shortest solution. We will refer to the start pole as Pole A, the end pole as Pole C, and the remaining pole as Pole B. Define ''Tk'' to be the number of moves our algorithm needs to solve the game for ''k'' disks. To solve the game with 1 disk, simply move the disk from Pole A to Pole C, so [[Image:Image7.JPG|thumb|Image 1: Note that this case must occur for the ''kth'' disk to move freely onto Pole C.|300px|right]] :$T_1=1$. Assume that we know an algorithm to move ''k'' -1 disks for ''k'' > 1 (so we also know the value of ''T''''k''-1). To solve the game with ''k'' disks, follow these steps: :1. Move the top ''k'' -1 disks on Pole A to Pole B using our algorithm, taking ''T''''k''-1 moves, as in Image 1.
:2. Move the ''kth'' disk to Pole C, taking 1 move, as in Image 2.
:3. Move the ''k'' -1 disks on Pole B on top of the ''kth'' disk on Pole C using our algorithm, taking ''T''''k''-1 moves. Hence we can describe the number of moves in our algorithm by the recursive formula: :$T_k=T_{k-1}+1+T_{k-1}=2T_{k-1}+1$ [[Image:Image8.JPG|thumb|Image 2: After taking 1 step to move the ''kth'' disk onto Pole C, all that is left to do is move the ''k'' -1 disks onto Pole C.|300px|right]]
We will now show by [[Induction|induction]] that our algorithm uses the least number of moves. The base case (''T''1 = 1) is satisfied because there is no way to solve the game without moving any disks. Assume that our algorithm takes the least number of moves to solve for ''k'' -1 disks for ''k'' > 1, so ''T''''k''-1 is '''minimal'''. To solve the game with ''k'' disks, the ''kth'' disk must be moved at some point, and moving it requires the top ''k'' -1 disks to be on the pole that is not the starting or ending pole. Since our algorithm needs the least number of moves to solve for ''k'' -1 disks, we will assume that moving the top ''k'' -1 disks takes ''T''''k''-1 moves. Note that it will be most efficient to move the kth disk directly from pole A to pole C. The other option would be to move the other k-1 disks to pole C, move the kth disk to pole B, then move the other k-1 disks back to pole A before the kth disk can reach pole C. This requires transferring those k-1 disks three times (to pole C, then pole A, then back to C), whereas our method of moving the kth disk directly to pole C only requires two such transfers. Thus the minimum number of moves required to solve for ''k'' disks assuming ''T''''k''-1 is minimized is :$T_{k-1}+1+T_{k-1}=2T_{k-1}+1=T_k$. ===The Explicit Formula=== We will show by [[Induction|induction]] that the explicit formula for the number of moves in this minimal algorithm is :$T_k=2^k-1$, where ''k'' is the number of disks. The base case is satisfied: :$T_1=2^1-1=2-1=1$ as desired. Assume the (''k'' -1)th case holds. Then :\begin{align} T_k & = 2T_{k-1}+1 \\ & = 2(2^{k-1}-1)+1 \\ & = 2(2^{k-1})-2+1 \\ & = 2^{k-1+1}-1 \\ & = 2^k-1 \end{align} Thus we have shown the minimal algorithm for any Towers of Hanoi game with ''k'' disks requires ''T''''k'' = 2''k'' – 1 steps. ==Back to the Legend== Now that we have the equation to determine the number of moves needed for any number of disks, we can verify the time we said was needed to complete the game in the legend. A Towers of Hanoi game with 64 disks will take: :$T_{64}=2^{64}-1=18,446,744,073,709,551,615\text{ moves}$ If the priests move 1 disk per second, then they will need: :$18,446,744,073,709,551,615\text{ s }\cdot \left(\frac{1\text{ min}}{60\text{ s}}\right)\left(\frac{1\text{ hr}}{60\text{ min}}\right)\left(\frac{1\text{ day}}{24\text{ hr}}\right)\left(\frac{1\text{ yr}}{365.25\text{ days}}\right)$ :::$\approx584.54\text{ billion years}$ Assuming that the Sun has a life span of 10 billion yearshttp://helios.gsfc.nasa.gov/qa_sun.html, the time predicted by the legend is $585.54 \div 10 \approx 58.5$ times longer than the Sun's lifespan. Algebra Analysis Calculus Dynamic Systems Fractals Geometry Graph Theory Number Theory Polyhedra Probability Topology Other None Algebra Analysis Calculus Dynamic Systems Fractals Geometry Graph Theory Number Theory Polyhedra Probability Topology Other None Algebra Analysis Calculus Dynamic Systems Fractals Geometry Graph Theory Number Theory Polyhedra Probability Topology Other Towers of Hanoi is a popular example in introductory computer science courses because programming it is instructional but relatively simple. The mathematical nature of the game teaches how to create recursive programshttp://apcentral.collegeboard.com/apc/members/courses/teachers_corner/45418.html, while the simple user interface of the game (which can be made using only rectangles) introduces the basics of programming graphics. In addition, the game's exponential solution is an example of why computer scientists dislike exponential time; it takes far too long to compute. Assuming the average computer can do 100 million operations per minute, then solving the game with 64 disks would take the computer 5845.42 years to complete. Towers of Hanoi is also a popular tool in psychological research; it can test problem solving capabilities.http://cognitivepsychology.wikidot.com/problem-solving:tower-of-hanoi Consequently, the game is often used to test intelligence. In the 2011 film ''Rise of the Planet of the Apes'', scientists test the intelligence of apes with Towers of Hanoi.http://www.imdb.com/title/tt1318514/synopsis The faster the apes solve the game, the more intelligent they are perceived to be. Yes, it is.