In the standard Towers of Hanoi problem, you have three poles: the first has a pyramid of n disks, and the other two are empty. Your task is to move the disks to the third pole, with the restriction that you can move one disk at a time, never putting a larger disk on top of a smaller one.

How many moves would this task take, if ALL moves had to be either to or from the middle pole? (Thus, you cannot move a disk directly from the first pole to the third one, or viceversa.)

If T(n) represents the moves required to shift the disks from 1st to 3rd tower, then:
T(n)=3*T(n-1)+2
Solving this equation yields: T(n)=2*sum(3^0...3^n)

Posted by And Or on 2006-08-07 11:09:31