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

The original Towers of Hanoi problem requires each block (n) to be move twice as often as block (n+1). The total number of moves required to move a tower of n blocks is ((2^n)-1).

The Towers of Hanoi Hard Hack problem requires each block to be moved (1) to the center pole, (2) off the center to the opposite pole, and (3) back to the center pole after the n+1 block is moved there.
In this manner, if it takes x moves to move the first n blocks to the center, it will take 3x+1 moves to move n+1 blocks to the center.
Or
f(n) = 3*f(n-1)+1 with f(1) = 1
This can be rewritten as f(n) = ((3^n)-1)/2
For 1 block     1 move
     2 blocks    4 moves
     3 blocks  13 moves
     4            40
     5          121
     6          364

Posted by Leming on 2006-04-23 18:26:53