Chapter 1.2, Problem 31ES

A Famous Puzzle The Tower of Hanoi is a puzzle invented by Edouard Lucas in 1883. The puzzle consists of three pegs and a number of disks of distinct diameters stacked on one of the pegs such that the largest disk is on the bottom, the next largest is placed on the largest disk, and so on as shown on page 26.

The object of the puzzle is to transfer the tower to one of the other pegs. The rules require that only one disk be moved at a time and that a larger disk may not be placed on a mailer disk. All pegs may be used.

Determine the minimum number of moves required to transfer all of the disks to another peg for each of the following situations.

a. You start with only one disk.

b. You start with two disks.

c. You start with three disks. (Note: You can use a stack of various size coins to simulate the puzzle, or you can use one of the many websites that provide a simulation of the puzzle.)

d. You start with four disks.

e. You start with five disks.

f. You start with n disks.

g. Lucas included with the Tower puzzle a legend about a tower that had 64 gold disks on one of three diamond needles. A group of priests had the task of transferring the 64 disks to one of the other needles using the same rules as the Tower of Hanoi puzzle. When they had completed the transfer, the tower would crumble and the universe would cease to exist. Assuming that the priests could transfer one disk to another needle every second, how many years would it take them to transfer all of the 64 disks to one of the other needles?