Tower of Hanoi

Material Required: Board with three rods, discs.

How to play:

We have a board with three rods. In one of the rods. We insert several discs arranged in order of magnitude with the largest at bottom. The task is to transfer all the discs from the first rod to one of the others in such a way that the final arrangement is the same as the original one. The rules are, only one discs can be moved at a time. No disc should be ever placed on the top of a disc smaller than itself. You can make use of one free rod while transferring.

Start with just two discs and count the minimum number of moves required to transfer the discs to one of the other rods using the third rod, then try it with three discs, 4 discs and so on. The aim is to find a rule which connects the number of moves with the number of discs.

Answer:

The minimum number of moves needed to transfer all the discs from one rod to the other rod in the required order is 2ⁿ-1, where n is the number of discs. For example, to transfer 5 discs you would need at least 31 moves.

Recursive relation:

Number of discs	Minimum number of steps required to transfer discs
1	1
2	3
3	7
4	15

When you want to shift all the 3 discs from one rod to another, first you need to shift the two discs on the top to another rod. Both of them have to be on the same rod as one rod has the largest disc and the third rod has to free for shifting the largest disc. Now you have seen that the no. of steps needed to shift two discs is 3. So you will need 3 steps, then you will shift the largest disc on the empty rod. And then you have to shift the remaining two on top of the largest disc, this needs another 3 steps. Hence the total no. of steps needed are 3 + 1 + 3.

See the table, observe the pattern and find number of moves for 5 discs,

Number of steps required to transfer n discs = 2ⁿ -1

Number of steps required to transfer (n+1) discs = 2(2ⁿ -1) +1= 2ⁿ⁺¹-1

Question:

• Why we need three rods not two rods?

• What would happened if we add one more rod?