Activity III: Tower of Hanoi (Grade Levels: 48)
About Math Concepts 
Proving the Pythagorean Theorem 
Magic Squares and Stars 
The Tower of Hanoi 
More Math Concepts
Standards:
Standard 2: Patterns, Functions, and Algebra
Standard 6: Problem Solving
Standard 9: Connections
Objectives:
Students will have the opportunity to:
 the number of moves necessary to solve the Tower problem with varying numbers of disks
 the amount of time to complete the solution under certain assumptions.
Activity 3
This is a middle school level activity that can be adapted to a higher level by increasing the number of poles and determining the minimum number of moves in that case. Lower levels may just play the game while the teacher watches the development of strategies.
The Tower of Hanoi
An
old legend tells of a Hindu temple where the pyramid
puzzle might have been used for the mental discipline
of young priests. The legend says that at the beginning
of time, the priests in the temple were given a stack
of 64 gold disks, each one a little smaller than the
one beneath it. Their assignment was to transfer the
64 disks from one of three poles to another, with one
important rule: a large disk can never be placed on
top of a smaller one. The priests worked very efficiently,
day and night. When they finished their work, the myth
said, the temple would crumble into dust, and the world
would vanish.
In
1883, Edouard Lucas, a French mathematician, invented
a game called the Tower of Hanoi (sometimes referred
to as the Tower of Brahma or the End of the World Puzzle).
The game begins with a number, for example of 3 discs,
arranged on one of three poles. Each disc is smaller
than the disc below it. The object is to move all the
discs from the starting tower to one of the remaining
towers. Only one disc can be moved at a time, and a
larger disc can never be placed on top of a smaller
one. Use the lowest number of possible moves.
The
following table records the minimum number of moves
required for the number of original discs.
Number of Discs

Minimum Moves

3

7

4

15

5

31







The
following web sites are Tower of Hanoi puzzles.
SuperKids Tower of Hanoi Page
http://www.superkids.com/aweb/tools/logic/towers/
Lawrence
Hall of Science Tower of Hanoi Facts and Games
http://www.lhs.berkeley.edu/Java/Tower/towerhistory.html
Andrew
Cumming's Tower of Hanoi Page
http://www.dcs.napier.ac.uk/~andrew/hanoi/rechelp.html
Werner
Moshammer's Tower of Hanoi Game
http://stud1.tuwien.ac.at/~e9125168/javaa/jtower.html
John J. Wills' Tower of Hanoi Game
http://www.sover.net/~jwills/hanoi.html
1. Play the game with three and five discs. Did you accomplish the game in the minimum moves?
2. Complete the table shown above. Determine a rule for the minimum number of moves.
3a. If you make one move every minute, what is the minimum number of minutes it should take to complete a game containing 5 discs?
3b. If you make one move every minute, what is the minimum number of days it should take to complete a game containing 15 discs?
4. Bonus: Working day and night and making one move per second, how long in years would it take the priests to complete the game? Hint: it would require 18,446,744,073,709,551,615 moves.
