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:
| Number of discs | Number of transfers |
|---|---|
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| n | 2^n - 1 |
Correctly solved by:
| 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 |