Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Tower of Hanoi


Date: 10/16/97 at 00:59:22
From: Forrest Bankston
Subject: Tower of Hanoi

I'm looking for mathematical solution, not a trial and error one.
I have done several net searches but can find no solution - just 
histories of the puzzle and games for trial-and-error fun.
My students are exasperated and want a mathematical model.
Can you help?

Muchly appreciated...
Forrest


Date: 10/16/97 at 10:15:49
From: Doctor Rob
Subject: Re: Tower of Hanoi

 Problem 1:  Move one disk from the top of pile A to pile B.
Solution 1:  Do it!

 Problem 2:  Move a stack of the two smallest disks from the 
             top of pile A pile to pile B.
Solution 2:  Move the small disk to the pile C. Move the large one
             to pile B. Move the small one to pile B.

 Problem 3:  Move a stack of the three smallest disks from the 
             top of pile A to pile B.
Solution 3:  Use Solution 2 (relabeling the piles B <-> C) to 
             move the two smallest disks to pile C. Move the 
             largest one to pile B.  Use Solution 2 (relabeling the 
             piles A <-> C) to move the two smallest ones to pile B.

 Problem 4:  Move a stack of the four smallest disks from the 
             top of pile A to pile B.
Solution 4:  Use Solution 3 (relabeling the piles B <-> C) to 
             move the three smallest disks to pile C. Move the 
             largest one to pile B. Use Solution 3 (relabeling the 
             piles A <-> C) to move the three smallest ones to pile B.

 Problem 5:  ...
Solution 5:  ...

...

 Problem n:  Move a stack of the n smallest disks from the top 
             of pile A to pile B.
Solution n:  Use Solution (n-1) (relabeling the piles B <-> C) to 
             move the n-1 smallest disks to pile C. Move the 
             largest one to pile B. Use Solution (n-1) (relabeling the 
             piles A <-> C) to move the n-1 smallest ones to pile B.

The trick is in keeping track of the relabeling during the process!

Example:  Move 4 disks from X to Y:
                            X     Y     Z
                 Start:  1234     -     -
 1. Move 1 from X to Z:   234     -     1
 2. Move 2 from X to Y:    34     2     1
 3. Move 1 from Z to Y:    34    12     -
 4. Move 3 from X to Z:     4    12     3
 5. Move 1 from Y to X:    14     2     3
 6. Move 2 from Y to Z:    14     -    23
 7. Move 1 from X to Z:     4     -   123
 8. Move 4 from X to Y:     -     4   123
 9. Move 1 from Z to Y:     -    14    23
10. Move 2 from Z to X:     2    14     3
11. Move 1 from Y to X:    12     4     3
12. Move 3 from Z to Y:    12    34     -
13. Move 1 from X to Z:     2    34     1
14. Move 2 from X to Y:     -   234     1
15. Move 1 from Z to Y:     -  1234     -

Notice the pattern of the disk being moved:  

   1,2,1,3,1,2,1,4,1,2,1,3,1,2,1.

On all odd numbered moves, you are moving disk 1. If the move number 
is 2 times an odd number, you are moving disk 2. If the move number 
is 4 times an odd number, you are moving disk 3. In general, if the 
move number is 2^n times an odd number, you are moving disk n+1.

Notice Steps 1-3 are Solution 2 with A = X, B = Y, C = Z.
Notice Steps 5-7 are also Solution 2 with A = Y, B = Z, C = X.
Notice Steps 9-11 are also Solution 2 with A = Z, B = X, C = Y.
Notice Steps 13-15 are also Solution 2 with A = X, B = Y, C = Z.

Notice Steps 1-7 are Solution 3 with A = X, B = Z, C = Y.
Notice Steps 9-15 are also Solution 3 with A = Z, B = Y, C = X.

You can plan the whole operation ahead. There will by 2^d-1 moves if
there are d disks. Move 2^(d-1) will be to move the largest disk from
X to Y. To do that, you must move the d-1 smaller disks off of X, but
not put them at Y, but at Z. That will take Steps 1 through 2^(d-1)-1.
Afterwards, you have to move the d-1 smaller disks from Z to Y. That
will take Steps 2^(d-1)+1 to 2^d-1. That divides the problem into two
smaller ones of the same kind. Now you plan each of those in a similar
way: the middle step will be moving the largest disk from its starting
place to the appropriate destination. The preceding steps will be to
get the smaller disks out of the way, and the following steps will be
to move the smaller disks to the destination.

Understood?  If not, write back, and we'll try to explain further or
differently.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   


Date: 10/16/97 at 14:14:07
From: Forrest Bankston
Subject: Re: Tower of Hanoi

Got it!  Thanks for the quick turnaround and detailed explanation.
- Forrest


    
Associated Topics:
High School Puzzles
Middle School Puzzles

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/