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

2 * Sigma [x=0 to n]  3^x-1 : n > 0

If there are 3 disks it would take 2* (3⁰ + 3¹ + 3²) = 26 moves.
For 7 disks it would take 2* (3⁰ + 3¹ + 3² + 3³ + 3⁴ + 3⁵ + 3⁶) = 2186 moves.

And so forth...

Edited on April 23, 2006, 9:23 pm

Posted by Dej Mar on 2006-04-23 18:45:33