4
$\begingroup$

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!

  • 1
    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](http://en.wikipedia.org/wiki/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.2012-01-12
  • 1
    @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.2012-01-12
  • 3
    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.2012-01-12
  • 0
    @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.2012-01-12
  • 2
    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.2012-01-12

2 Answers 2

2

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$.

  • 0
    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!2012-01-12
  • 0
    @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 terms2012-01-13
  • 0
    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.2012-05-26
  • 0
    It is very similar to this question I asked: http://math.stackexchange.com/questions/143258/adapted-towers-of-hanoi-from-concrete-mathematics-number-of-arrangements.2012-05-26
  • 0
    @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$.2012-05-26
  • 0
    @Henry: You are right, it is different, then. In this case, it is actually similar to an another question to which I answered recently: http://math.stackexchange.com/questions/14489/proof-of-clockwise-towers-of-hanoi-variant-recursive-solution/149453#149453. The $m_{AC}(n)$ here is the same as the $R_n$ in this other question.2012-05-26
  • 0
    @Henry: ...On the other hand, although direct moves from C to A are allowed, I'm not sure whether direct moves from C to B are necessarily not allowed (if they are not, then the question I mentioned in the previous comment - http://math.stackexchange.com/questions/14489/proof-of-clockwise-towers-of-hanoi-variant-recursive-solution/149453#149453 - is equivalent).2012-05-26
  • 0
    Now I see that direct moves from C to B are allowed (from your example of moving n disks from C to B, step 2). In that case, the question I pointed out in the previous post is not equivalent.2012-05-26
2

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$.

  • 0
    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.2012-01-13
  • 0
    @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.2012-01-13