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
Math Forum Home || Math Library || Quick Reference || Math Forum Search