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.

Click here for a Tower of Hanoi puzzle site.

1. Play the game using 3, 4, 5, and 6 discs.

2. Construct a table showing the minimum number of moves for a given number of disks. Determine a rule for the minimum number of moves.

Number of disks

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.

The above copied from:

http://www.pbs.org/teachersource/mathline/concepts/historyandmathematics/activity3.shtm