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