Tower of Hanoi
Paul Eubanks Washington High School
3535 E. 114th Street
Chicago, Illinois 60617
312-646-4860
Objectives:
(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 = 2n - 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 264 - 1. The answer is approximately
589,942,417,400 years.
Return to Mathematics Index