# Optimal Towers of Hanoi strategy (3 pillars, from pillar A directly to C not allowed)

I am working on a exercise where I need to find the number of steps (Tn) for solving the Towers of Hanoi while having three pillars (A, B, C). All disks (n) are placed at pillar A and need to be moved to pillar C. It is not allowed to move a disk from pillar A to pillar C directly, all disks have to pass pillar B.

I don't know where to start, I tried to write down an example for 2 and 3 discs but at four disks I had the idea I was doing a lot more moves than actually needed.

Any help is appreciated,

Thanks!

-
What do you mean "It is not allowed to move a disk from pillar A to pillar C directly"? The second move has to be from A to C, at least in the Tower of Hanoi that I know... By the way, this is a classic problem and the linked to wikipedia article has lots of spoilers. I suggest you don't look past the introduction. – Simon Jan 12 '12 at 12:59
@Simon: Move the top disk from $A$ to $B$, then move it from $B$ to $C$; this counts as two moves in the restricted problem. – Brian M. Scott Jan 12 '12 at 13:05
Hint: You need to get the largest disk ($n$) from $A$ to $B$ first (since you can't jump right to $C$). In order to make that move, the remaining disks ($1$ to $n-1$) have to be on pillar $C$. How many moves does it take to move them there? Then you need to move the largest disk from $B$ to $C$; the remaining disks at that point need to be on pillar $A$; and finally the remaining disks need to move back to pillar $C$. So you've moved the largest disk twice, and the remaining $n-1$ disks from $A$ to $C$, then back to $A$, then back to $C$. This should give a recurrence relation. – mjqxxxx Jan 12 '12 at 13:10
@Brian: Oh yeah. I guess that means my brain has stopped working for the night and it's time to go to bed. Sorry about the confusion. – Simon Jan 12 '12 at 13:19
If it's the case that direct moves from $C$ to $A$ are allowed (i.e., there are exactly five legal moves: $AB$, $BA$, $BC$, $CA$, and $CB$), this should be clarified... if so, the recurrence relation I described isn't complete; you need a complementary recurrence relation for moving $n$ disks from $C$ to $A$, too, since they're not the same. – mjqxxxx Jan 12 '12 at 22:01

Using Henry’s notation, the system of recurrences is

\left\{\begin{align*} &m_{AC}(n+1)=2m_{AC}(n)+m_{CA}(n)+2\\ &m_{CA}(n+1)=m_{CB}(n)+m_{BA}(n)+1\\ &m_{AB}(n+1)=m_{AC}(n)+m_{CB}(n)+1\\ &m_{BA}(n+1)=m_{BC}(n)+m_{CA}(n)+1\\ &m_{BC}(n+1)=m_{BA}(n)+m_{AC}(n)+1\\ &m_{CB}(n+1)=m_{CA}(n)+m_{AB}(n)+1\;. \end{align*}\right.

Then \begin{align*} m_{CA}(n+1)&=m_{CB}(n)+m_{BA}(n)+1\\ &=2m_{CA}(n-1)+m_{AB}(n-1)+m_{BC}(n-1)+3\\ &=2m_{CA}(n-1)+2m_{AC}(n-2)+m_{CB}(n-2)+m_{BA}(n-2)+5\\ &=2m_{CA}(n-1)+2m_{AC}(n-2)+m_{CA}(n-1)+4\\ &=3m_{CA}(n-1)+2m_{AC}(n-2)+4\;. \end{align*}

On the other hand, $m_{CA}(n)=m_{AC}(n+1)-2m_{AC}(n)-2$, so \begin{align*} m_{CA}(n+1)&=m_{AC}(n+2)-2m_{AC}(n+1)-2\;,\\ m_{CA}(n-1)&=m_{AC}(n)-2m_{AC}(n-1)-2\;, \end{align*}

and hence \begin{align*} m_{AC}(n+2)-2m_{AC}(n+1)-2&=m_{CA}(n+1)\\ &=3m_{CA}(n-1)+2m_{AC}(n-2)+4\\ &=3m_{AC}(n)-6m_{AC}(n-1)+2m_{AC}(n-2)-2\;, \end{align*}

or $$m_{AC}(n+2)=2m_{AC}(n+1)+3m_{AC}(n)-6m_{AC}(n-1)+2m_{AC}(n-2)\;.$$

Finally, shifting indices gives us $$m_{AC}(n)=2m_{AC}(n-1)+3m_{AC}(n-2)-6m_{AC}(n-3)+2m_{AC}(n-4)\;.$$

By direct computation the initial values are $m_{AC}(0)=0$, $m_{AC}(1)=2$, $m_{AC}(2)=7$, and $m_{AC}(3)=19$. The sequence continues $47, 113, 267, 629$ and is not in OEIS.

The auxiliary equation is $x^4-2x^3-3x^2+6x-2=0$, which reduces to $$(x-1)(x^3-x^2-4x+2)=0\;.$$ The cubic factor has three real roots; I didn’t feel like writing down the exact expressions for them, but this cubic equation calculator says that they are approximately \begin{align*}&2.34292308277717\;,\\ -&1.81360650264833\;,\text{ and}\\ &0.47068341987116\;. \end{align*}

In the long run the first will dominate, and the sequence will grow by approximately that factor with each increase of one in the number of disks. For the record, $629/267\approx 2.3558$.

-
That's interesting: I originally had $m_{AC}(n)=112$ rather than $113$, and then greater divergence, so it seems I may have made a minor error somewhere. And checking, it seems I did, so I now agree with your figures. Changing mine. – Henry Jan 13 '12 at 8:06
@Henry: It’s a pretty ugly result; I can’t help wondering whether the original problem was supposed to be the number of moves in the cyclic version of the puzzle, with only $A\to B\to C\to A$ allowed. – Brian M. Scott Jan 13 '12 at 8:30

To move $n$ disks from $A$ to $C$ you need to move

1. $n-1$ disks from $A$ to $C$
2. disk $n$ from $A$ to $B$
3. $n-1$ disks from $C$ to $A$
4. disk $n$ from $B$ to $C$
5. $n-1$ disks from $A$ to $C$

To move $n$ disks from $C$ to $A$ you need to move

1. $n-1$ disks from $C$ to $B$
2. disk $n$ from $C$ to $A$
3. $n-1$ disks from $B$ to $A$

To move $n$ disks from $A$ to $B$ you need to move

1. $n-1$ disks from $A$ to $C$
2. disk $n$ from $A$ to $B$
3. $n-1$ disks from $C$ to $B$

To move $n$ disks from $B$ to $A$ you need to move

1. $n-1$ disks from $B$ to $C$
2. disk $n$ from $B$ to $A$
3. $n-1$ disks from $C$ to $A$

To move $n$ disks from $B$ to $C$ you need to move

1. $n-1$ disks from $B$ to $A$
2. disk $n$ from $B$ to $C$
3. $n-1$ disks from $A$ to $C$

To move $n$ disks from $C$ to $B$ you need to move

1. $n-1$ disks from $C$ to $A$
2. disk $n$ from $C$ to $B$
3. $n-1$ disks from $A$ to $B$

This translates into six recurrence relations. For example

$$m_{AC}(n)=2+2m_{AC}(n-1)+m_{CA}(n-1)$$

and with all six you can then calculate this for $n$ as large as you like. For example (corrected:) $m_{AC}(20)=40424579$.

-
Thanks Henry for your explanation and efforts in this answer! I am sorry but how did you come to you answer in your example with 20 discs? Thanks once again! – Jef Jan 12 '12 at 23:46
@Jef: I produced the same system of recurrences as Brian M. Scott and starting at $m_{AC}(0)=m_{CA}(0)=m_{AB}(0)=m_{BA}(0)=m_{BC}(0)=m_{CB}(0)=0$ ran through the next twenty terms – Henry Jan 13 '12 at 8:10
Notice that (if I'm not mistaken) $m_{AC}(n)$ and $m_{CA}(n)$ are actually the same. If we call it $T(n)$, we have that $T(n) = 3T(n-1) + 2$, which makes it much easier to solve. – anonymous May 26 '12 at 12:18
It is very similar to this question I asked: math.stackexchange.com/questions/143258/…. – anonymous May 26 '12 at 12:20
@anonymous: I think in this question you cannot move directly from A to C but can move directly from C to A. Your linked question stopped both direct moves. So here $m_{AC}(1)=2$ but $m_{CA}(1)=1$. – Henry May 26 '12 at 12:55