Cyclic tower of hanoi problem

Question

If I have 3 rods in a circle and it is allowed to move the disks only in the clockwise direction. How many moves is necessary to move n disks from first rod to the third rod?

Answer 1

Nice variation on a classic problem!

Here is an answer for a sufficient number of moves, I am not sure if this number is actually necessary.

Let $a_n$ be the number of moves taken to advance $n$ discs by one step, and $b_n$ the number taken to advance the $n$ discs by two steps.

To advance by one step we can do the following:

• advance the top $n-1$ discs by two steps (if they have to go round the circle and back on top of the largest disc, this will never be a problem); this leaves the second peg vacant
• advance the largest disc by one step
• advance the $n-1$ discs by two steps

Therefore $$a_n=2b_{n-1}+1\ .$$ Similarly we can find $$b_n=b_{n-1}+1+a_{n-1}+1+b_{n-1}=2b_{n-1}+a_{n-1}+2\ .$$ Substituting the first recurrence into the second gives $$b_n=2b_{n-1}+2b_{n-2}+3\ ,$$ and this recurrence can be solved by the standard method using the characteristic equation. In this case the answer works out as $$b_n=\frac{(1+\sqrt3)^{n+2}-(1-\sqrt3)^{n+2}}{4\sqrt3}-1\ .$$

Addendum. After some more thought I am reasonably sure this number of moves is necessary. For example in the first step you have to move the top $n-1$ discs onto the third peg, otherwise the largest disc cannot be moved at all. Then you have to move the largest disc one peg, then you have to get the other discs back on top of it.