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.