Return to Mathematics IndexTower of Hanoi

Paul Eubanks Washington High School

3535 E. 114th Street

Chicago, Illinois 60617

312-646-4860Objectives:

(For grades 6 through 12)

1. To discover a pattern.

2. To evaluate an exponential expression.Materials:

Tower of Hanoi puzzle and circular discs of various sizes.Procedure:

Pass out five circular discs of different sizes to each student. Have each

student draw three large circles on a sheet of paper. Then have them place the

largest disc in one of the circles as you place the largest disc of the puzzle

on one of the three pegs (towers). Explain the rules of the puzzle as follows.

The object is to move all the discs from one tower (one circle) to another tower

(another circle). Only one disc can be moved at a time and a larger disc can

never be placed on top of a smaller one. The discs should be moved from one

tower to another in the least number of moves.

With one disc it only takes one move to place that disc on another tower

(circle). Next have the students place the two largest discs in any circle.

Have the students try to move the two discs to another circle. Ask them to tell

how many moves it took. It will take three moves. Place the smaller disc in

either open circle. Then move the larger disc to the other open circle.

Finally place the smaller disc on top of the larger disc. Now have the students

place the three largest discs in any circle. Allow the students some time to

try to move the three discs to another circle. This will take at least seven

moves. Move the top two discs to another circle in three moves as explained

above. Next move the largest disc to the open circle. Then use three moves to

get the two smaller discs on top of the largest disc. Now have the students

place the four largest discs in any circle and try to move them to another

circle. This will take at least 15 moves. It will take seven moves to move the

top three discs to another circle as we just did with three discs in a circle.

After moving the top three discs, the largest disc is moved to the open circle.

Next the other three discs must be moved on top of this largest disc. This will

take seven more moves, however, the first move is crucial. When moving an odd

number of discs, you must move the first disc to the circle (tower) that you

want all the discs to end up on. When moving an even number of discs you must

move the first disc to the circle that you do not want the discs to end up on.

At this point you should have the students notice how the number of moves

increased, i.e., 1, 3, 7 and 15. Have the students look for a pattern and

predict the number of moves for five discs. The number is 31. Give the

students a few minutes to see if anyone can come up with the formula - which is

M = 2^{n}- 1 where M is the number of moves and n is the number of discs. If

no one comes up with the formula give it to them and have them verify it for n

equal to 1, 2, 3, 4, and 5. Next have them use the formula to find out the

number of moves for 6, 7, 8, and 10 discs. Finally tell them about the legend

that a monk has 64 discs on a tower and he moves one every second. When he has

moved all the discs the world will end. Have them estimate how long this would

be.

Use a calculator to evaluate 2^{64}- 1. The answer is approximately

589,942,417,400 years.