Illuminations: Tower of Hanoi

# Tower of Hanoi

The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks (initially three in the applet below), initially stacked in increasing size on one of three pegs.

The goal is to move all the discs from the left peg to the right one.Try to move all the discs using the smallest number of moves possible. Compete against a friend to see who can solve the puzzle in the shortest time or with the fewest number of moves. This applet is based on the Tower of Hanoi Applet created by David Herzog, www.mazeworks.com.

### Instructions

 The object of the game is to move all of the disks to the peg on the right. Click-and-drag to move a disc. Only one disc may be moved at a time. A disc can be placed either on an empty peg or on top of a larger disc. Click the Timer checkbox to turn the timer on or off. Vary the difficulty by changing the number of discs. The + and - buttons increase and decrease the number of discs. You will likely have no problem with three discs, but can you solve the puzzle with 12 discs? If you need help, select Solution to watch the computer solve the puzzle. The Speed slide determines how fast the discs move. Restart returns all of the disks to the left peg.

### Exploration

 If you’ve played the game as well as possible, you should have discovered that the minimum number of moves for 1, 2, 3, and 4 disks, respectively, is 1, 3, 7, and 15. If it took you more moves than that, then press the Solution button and watch the computer solve the tower in the minimum number of moves. To figure out how many turns it’ll take for more than 4 disks, find a pattern relating the number of disks to the minimum number of turns it takes to win the game. Write down the minimum number of moves for 1, 2, 3, and 4 disks on a piece of paper. Do you see a pattern? (Hint: Add 1 to each of the numbers. Recognize a pattern now?) Using the timer and a fixed speed setting, measure how long it takes to solve the problem for different number of discs. How long would it take to move 20 disks? 50? 100? Some experts suggest that computing speeds doubles approximately every six months. How long before this applet will be able to finish 100 disks in a second?

### Lessons

 More and Better Mathematics for All Students
 © 2000 National Council of Teachers of Mathematics Use of this Web site constitutes acceptance of the Terms of Use The National Council of Teachers of Mathematics is a public voice of mathematics education, providing vision, leadership, and professional development to support teachers in ensuring mathematics learning of the highest quality for all students. The views expressed or implied, unless otherwise noted, should not be interpreted as official positions of the Council.