$5.(10$ points$)$

We discussed an algorithm to solve the Tower of Hanoi problem in class. The approach we

discussed for optimally moving n disks from peg A to peg B using peg C can be illustrated

as shown below:$2*$ Move$($n$1)+1$

A B

C

$1)$ Move$($n$1)$

$2)$ Move last disk

$3)$ Move$($n$1)$

$*$ Steps are numbered from $1$ to $3.$

Therefore, number of moves in Move$($n$)$ is:

Now consider the following variant of the Tower of Hanoi problem. To the original problem,

let us add a new condition: Each disk move now must be performed only in the clockwise

direction $$ ie$.,$ A $->$ B$,$ B $->$ C$,$ or C $->$ A$.$ So$,$ for example, if I have to move a disk from A

to C then that will involve a minimum of two moves $($first$,$ from A to B$,$ and then from B to

C$)$; but from C to A needs only one move. All the old conditions from the original version of

the problem still apply $($i$.$e$.,$ you cannot move a larger disk on top of a smaller disk$).$

Under this new problem formulation:

$$ Let Q$($n$)$ denote the minimum number of moves required to transfer n disks from A $->$ B

using C$.$

$$ Let R$($n$)$ denote the minimum number of moves to transfer n disks from A $->$ C

clockwise using B$.$

Prove that:

Q$($n$)=$

$$

$$

$$

$1,$ n $=1$

$2$R$($n $1)+1,$ n $>1$

$(1)$

R$($n$)=$

$$

$$

$$

$2,$ n $=1$

Q$($n$)+$ Q$($n $1)+1,$ n $>1$

$(2)$

Hint $1$: To provide the proof you may need to first come up with a corresponding algorithm

under the new clockwise condition. That should give you the mathematical recurrence shown

above. Please illustrate your algorithm in the form of a figure$$following the example of the

figure shown above in the question, for the original version of the problem.

Hint: If R$($n$)$ is the number of moves required to move n disks from peg A to peg C $($using

B$),$ then how many moves will be needed to move n disks from peg B to peg A $($using C$)?$