TIFR CSE 2011 | Part B | Question: 29

Question

You are given ten rings numbered from $1$ to $10$, and three pegs labeled $A$, $B$, and $C$. Initially all the rings are on peg $A$, arranged from top to bottom in ascending order of their numbers. The goal is to move all the rings to peg $B$ in the minimum number of moves obeying the following constraints:

1. In one move, only one ring can be moved.
2. A ring can only be moved from the top of its peg to the top of a new peg.
3. At no point can a ring be placed on top of another ring with a lower number.

How many moves are required?

• A. $501$
• B. $1023$
• C. $2011$
• D. $10079$
• E. None of the above.

Comments

Extra information

Its time complexity is O(2^n)

the recurrence relation is T(n) = 2 T(n-1) +1 , T(1) = 1

Answer 1

I think its Tower of Hanoi problem.
Therefore, total number of function call $2^{n} -1 = 1023$.

 $\therefore$ Option $B$.

Comments

yes it is tower of hanoi problem problem

---

1023 will be total Moves but not function calls.In TOH recursive we will call for TOH(0) also and it will be a function call but not a move.

fxn calls will be 2047 i guess but moves are 1023.Every function call will not give a move.Some will return from base condition

---

By generalizing the problem with 3 rings, we can say that for 'n' rings :

Total function calls=2ⁿ⁺¹-1

Total number of moves=2ⁿ-1  (better to draw the tree, then answer)

Answer 2

it is a tower of hanoi problem. we can see recurrence relation for moves.

number of moves:

$T(0) = 0$

$T(1) = 1$

$T(2) = 3$

$T(3) = 7$

$T(4) = 15$

.

.

.

$T(10) = T(9) +T(9) +1$

$T(n) = T(n-1) +T(n-1) +1$

 $T(n) = 2T(n-1) +1$

           $= (2^n)-1$

           $=1023$

 so B is ans

Comments

This should be the best answer.

Answer 3

best blog about Tower of Hanoi :

https://www.hackerearth.com/blog/algorithms/tower-hanoi-recursion-game-algorithm-explained/