The Tower of Hanoi Problem. r circular rings of tapering sizes are slipped into

Question

The Tower of Hanoi Problem. r circular rings of tapering sizes are slipped into a peg with the largest ring at the bottom, as shown in Fig. 10P.1 in page 338 of textbook. These rings are to be transferred one at a time onto another peg, and there is a third peg available on which rings can be left temporarily. If, during the course of transferring the rings, no ring may ever be replaced on top of a smaller one, in how many moves can these rings be transferred with their relative positions unchanged?

Explanation / Answer

The Tower of Hanoi problem asks us to move n eings from peg A (say) to peg C. The steps involved in the algorithm are:

1. Move n-1 rings (all except the biggest ring) from peg A to peg B.

2. Move the nth (biggest ring) from peg A to peg C.

3. Move the n-1 rings from peg B to peg C.

Amazingly, 1 and 3 are identical to the problem itself, that is they ask us to move n-1 rings from one peg to another. In other words if we write the tower of hanoi function as F(A,B,C,n), then the solution would be:

F(A,B,C,n) = F(A,C,B,n-1) + F(A,B,C,1) + F(B,A,C,n-1)

If the number of iterations needed is taken as f(n) for n rings, we have

f(n) = f(n-1) + 1 + f(n-1)

With f(1) = 1

=> f(n) = 2*f(n-1) +1 = 2*[2*f(n-2)+1]+1 = 22f(n-2)+2+1

=> f(n) = 22 [2f(n-3)+1] +2+1

=> f(n) = 23 f(n-3) + 22 + 2 + 1

......

=> f(n) = 2n-1 f(1) + 2n-2 + 2n-3 + ......... 2 + 1

=> f(n) = 2n-1 + 2n-2 + 2n-3 + ......... 2 + 1

The terms in the RHS consitute a G.P

=>  f(n) = 1 * (2n-1) / (2-1)

=>  f(n) = 2n-1

Thus it takes 2n-1 moves to move the rings.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.