Answer to May 31, 1999 Problem |
|---|
The Tower of Hanoi
As I watched my grandson James play with a
children's toy consisting of a peg with rings
of increasing size, I was reminded of the Tower
of Hanoi Puzzle.
This puzzle originated in 1883. It consists of
three pegs fastened to a stand, and of eight
circular discs of wood, each of which has a hole
in the middle through which a peg can be passed.
These discs are of different radii, and
initially, they are placed all on one peg. The
biggest is at the bottom, and the radii of the
successive discs decrease as you ascend, so the
smallest disc is on top. This arrangement is
called the Tower.
The problem is to shift the discs from one peg
to another in such a way that a disc shall never
rest on one that is smaller than itself, and
finally to shift the Tower from the
initial peg to one of the other two pegs.
Determine the smallest number of moves required
to transfer the Tower.
|
||||||||||||||
|
Answer to Problem:
It will take 255 transfers to move all eight
discs to one of the other pegs. Try experimenting with 2 discs, then with 3 discs, and set up a table:
|
| 1. Matt Garber | Winchester, VA |
| 2. Kat Bronson | Winchester, VA |
| 3. Rachel Rasmussen | Winchester, VA |
| 4. Jon Pence | Winchester, VA |
| 5. Liz Cotter | Centreville, VA |
| 6. Bob Hearn | Winchester, VA |