`Tower of HanoiPaul 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 = 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.                               `