Towers of Hanoi
From Math Images
Line 20: | Line 20: | ||
===Example of Solving the Game=== | ===Example of Solving the Game=== | ||
Solving Towers of Hanoi with 4 disks. {{Hide|1=[[Image:Hanoi.gif]]}} | Solving Towers of Hanoi with 4 disks. {{Hide|1=[[Image:Hanoi.gif]]}} | ||
+ | |||
|ImageDesc===The Recursive Solution== | |ImageDesc===The Recursive Solution== | ||
Line 64: | Line 65: | ||
:<math>18,446,744,073,709,551,615\text{ seconds}=\left(\frac{1\text{ minute}}{60\text{ seconds}}\right)=\left(\frac{1\text{ hour}}{60\text{ minutes}}\right)=\left(\frac{1\text{ day}}{24\text{ hours}}\right)=\left(\frac{1\text{ year}}{365.25\text{ days}}\right)\approx584.54\text{ billion years}</math> | :<math>18,446,744,073,709,551,615\text{ seconds}=\left(\frac{1\text{ minute}}{60\text{ seconds}}\right)=\left(\frac{1\text{ hour}}{60\text{ minutes}}\right)=\left(\frac{1\text{ day}}{24\text{ hours}}\right)=\left(\frac{1\text{ year}}{365.25\text{ days}}\right)\approx584.54\text{ billion years}</math> | ||
- | |||
Assuming that the Sun has a life span of 10 billion years, the time predicted by the legend is <math>585.54\div10\approx58.5</math> times longer than the Sun's lifespan. | Assuming that the Sun has a life span of 10 billion years, the time predicted by the legend is <math>585.54\div10\approx58.5</math> times longer than the Sun's lifespan. | ||
+ | |||
+ | |WhyInteresting=To solve a Towers of Hanoi game with k disks, we need at least <math>2^k-1</math> moves. | ||
+ | |||
|AuthorName=WikiBooks User GeniXPro | |AuthorName=WikiBooks User GeniXPro | ||
|SiteURL=http://upload.wikimedia.org/wikibooks/en/4/45/Hanoi_10Ring_3D_Small.jpg | |SiteURL=http://upload.wikimedia.org/wikibooks/en/4/45/Hanoi_10Ring_3D_Small.jpg | ||
|Field=Other | |Field=Other | ||
- | |||
|InProgress=Yes | |InProgress=Yes | ||
}} | }} |
Revision as of 15:50, 23 May 2013
- The Towers of Hanoi is a well known puzzle game based on a Hindu legend. According to the story, 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. However, whether the game was inspired by the legend, or the other way around, is unknown.
Towers of Hanoi |
---|
Contents |
Basic Description
The standard game begins with 3 poles, one of which (typically the leftmost) has some whole 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 start tower (typically the leftmost) to the specified end tower (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 rod onto the top of another rod.
- Each disk must be placed on a larger disk.
To fully understand the end of the world legend, one must understand the relationship between the number of disks and the amount of moves. As it turns out, this relationship is exponential; if the priests 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 Sun, the legend overestimates the amount of time we have until the world ends (unless we can someday live without the Sun).
Play the Game
You can play the game Towers of Hanoi right here! This applet will help you understand how the game works.
Example of Solving the Game
Solving Towers of Hanoi with 4 disks.
A More Mathematical Explanation
The Recursive Solution
This game becomes more interesting when we try to figure out the quickest [...]The Recursive Solution
This game becomes more interesting when we try to figure out the quickest solution to any Towers of Hanoi game. We will first reason through the ideal minimum amount of steps to solve a game with k-disks, then provide an algorithm that requires the same amount of moves as this ideal minimum. Define to be the minimum amount of moves needed for k disks. It is obvious that:
- and
Assume that we know is true. Note that to move the k^{th}(bottom) disk, we must first move the top k-1 disks. In addition, we must move the k^{th} disk at least (and hopefully only) once. Finally, the top k-1 disks must be placed on top of the k^{th} disk at some point to complete the game. Thus, the ideal recursive function for is:
Now we will provide an algorithm that requires the same amount of steps as . Since and do not change, we can assume that the (k-1)^{th} game is solvable. One algorithm to solve the k^{th} game is as follows:
- 1. Move the top k-1 disks to Pole B (assuming we start on Pole A and end on Pole C).
- 2. Move the k^{th} disk to Pole C.
- 3. Move the k-1 disks on Pole B to Pole C, on top of the k^{th} disk.
The total steps for this are:
Thus our ideal minimum function is a plausible solution to any Towers of Hanoi game.
The Non-Recursive Equation
We will show by induction that the non-recursive equation is
The base case is satisfied:
- as desired.
Assume the (k-1)^{th} case holds. Then
Thus we have shown the non-recursive equation holds for any Towers of Hanoi game with k disks.
Back to the Legend
Now that we have the equation to determine the amount of moves needed for any number of disks, we can verify the numbers listed in the Basic Description. A Towers of Hanoi game with 64 disks will take:
If the priests move 1 disk per second, then they will need:
Assuming that the Sun has a life span of 10 billion years, the time predicted by the legend is times longer than the Sun's lifespan.
Why It's Interesting
To solve a Towers of Hanoi game with k disks, we need at least moves.
Teaching Materials
- There are currently no teaching materials for this page. Add teaching materials.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.