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