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!

  • 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
    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
    @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