Question

If a total number of m moves are required to complete a Tower of Hanoi problem with 3 poles and p disks. Then, how many moves are needed to solve the porblem with (p+1) disks?

Answer 1

The number of moves required to solve the Tower of Hanoi with p+1 disks is 2m + 1, where m is the number of moves for p disks (m = 2^p - 1).

Step-by-step explanation:

When solving the Tower of Hanoi problem with 3 poles and p disks, the total number of moves required is given by m = 2^p - 1. To find the number of moves needed to solve the problem with p+1 disks, we apply the same formula: m = 2^(p+1) - 1. So if m moves are needed for p disks, then for p+1 disks, we need m moves to move the first p disks to the intermediate pole, 1 move to transfer the largest disk to the destination pole, and then another m moves to transfer the p disks on top of the largest disk, totaling 2m + 1 moves.

Example: If 3 disks require 7 moves (m = 2^3 - 1), then 4 disks will require 15 moves (m = 2^(3+1) - 1 or 2*7 + 1).

Answer 2

Step-by-step explanation:

the number of moves needed goes along with the power of 2 (minus 1).

with 1 disk we need 1 move (2¹ - 1).

with 2 disks we need 3 moves (2² - 1).

with 3 disks we need 7 moves (2³ - 1).

with 4 disks we need 15 moves (2⁴ - 1).

with 5 disks we need 31 moves (2⁵ - 1).

and so on.

for p disks we have to move the previous smaller tower (p-1 disks) one time to the middle pole, then move the additional disk to the 3rd pole, and then move the p-1 tower a second time now to the 3rd pole.

in other words, the p-disk tower has to move the p-1-disk tower twice plus the one move of the pth disk.

so,

mp = 2×mp-1 + 1

therefore,

m(p+1) = 2×m + 1