(a)
What is the smallest number of moves required to transport 2 disks to another pillar?
Print preview
Worksheet Preview Activity
Letβs get a feel for the sequence from the Towers of Hanoi puzzle. Use Figure 4.1.1 to answer the following questions.
1.
(b)
What is the smallest number of moves required to transport 3 disks to another pillar?
(c)
What is the smallest number of moves required to transport 4 disks to another pillar?
(d)
To find the smallest number of moves required to transport 5 disks to another pillar, letβs try to relate this task to the task of moving 4 disks. How many moves do each of the following tasks require?
-
Move the 4 smallest disks to the second pillar: moves.
-
Move the largest disk to the third pillar: moves.
-
Move the 4 smallest disks to the third pillar (on top of the largest disk): moves.
Therefore, the smallest number of moves required to move five disks is:
(e)
Generalize the last observation. Let
