[Math] Modified tower of hanoi

discrete mathematicsrecurrence-relations

In the Tower of Hanoi puzzle , suppose our goal is to transfer all n disks from peg 1 to peg 3, but we cannot move a
disk directly between pegs 1 and 3 . Each move of a disk
must be a move involving peg 2 . As usual , we cannot
place a disk on top of a smaller disk.

My Attempt/Approach-:

Using Basic Tower of Hanoi,our goal is to transfer $n$ disks from peg1 to peg2 using peg3.

Steps-:

1. Transfer n-1 disks from peg1 to peg3 using $H_{n-1}$.

2. Move the $n$th disk from peg1 to peg2 (only 1 movement).

3. Transfer n-1 disks from peg3 to peg2 using $H_{n-1}$.

so,We are done with $H_{n}=2H_{n-1}+1$.

But,i am not getting how to solve this algorithm using the restriction that " Each move of a disk must be a move involving peg 2." I know the solution to this question is here,so i am writing steps as i get is

Steps-:

1. Transfer n-1 disks from peg1 to peg3 using $H_{n-1}$.

2. Move the $n$th disk from peg1 to peg2 (only 1 movement).

3. Transfer n-1 disks from peg3 to peg2 using $H_{n-1}$

giving the same recurrence relation ..where i am wrong??

Best Answer

  1. Recursively transfer $n-1$ disks from peg $1$ to peg $3,$ with every move involving peg $2.$

  2. Move the one disk currently on peg $1$ to peg $2.$ (This uses peg $2,$ as required.)

  3. Recursively transfer $n-1$ disks from peg $3$ back to peg $1,$ with every move involving peg $2.$

  4. Move the one disk currently on peg $2$ to peg $3.$ (This uses peg $2,$ as required.)

  5. Recursively transfer $n-1$ disks from peg $1$ to peg $3,$ with every move involving peg $2.$

Of course, when the recursive transfer calls for moving $0$ disks, there's nothing to do (that's the base of the recursion).

Related Question