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?
- A.
00100
- B.
00011
- C.
00010
- 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.