Consider Tower of Hanoi problem with poles, Counting binary digits

Consider a Tower of Hanoi problem with 3 poles A, B and C. Counting binary digits is analogous to the Tower of Hanoi problem. Let a variable x store the binary digits corresponding to each state after every movement of discs among the poles. For example, consider 3 discs a, b and c on pole A, where c is the largest and a is the smallest. This initial state means x = 000. When disc a is transferred from pole A to pole B, x becomes 001. When disc b is transferred from pole A to pole C, x becomes 010, and so on. If x = 00000 is considered state 1 of the Tower of Hanoi problem, then what is the value of x at state 4?

  1. A.

    00100

  2. B.

    00011

  3. C.

    00010

  4. D.

    01000

Attempted by 216 students.

Show answer & explanation

Correct answer: B

Since x = 00000 is state 1, the binary state value increases by 1 after each move. Therefore, state n corresponds to the binary value n - 1.

State 1: 00000
State 2: 00001
State 3: 00010
State 4: 00011

So, at state 4, x = 00011. Hence, Option B is correct.

Explore the full course: Dsssb Tgt Computer Science Paper 2