Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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 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
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. –  Brian M. Scott Jan 12 '12 at 13:05
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. –  mjqxxxx Jan 12 '12 at 13:10
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. –  mjqxxxx Jan 12 '12 at 22:01
1  
"exercise" in the sense of homework? (That would explain this simultaeneous duplicate). If so, please add the (homework) tag. –  joriki Jan 12 '12 at 22:11
show 2 more comments

2 Answers

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.