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

(In reply to Solution by Dej Mar)

I got the same solution as Dej Mar, so perhaps I'll post a small explanation. 

Clearly for n = 1 it would take 2 moves.

For n > 1, consider the largest plate.  It must eventually reach the 3rd pole, and it must move there from the 2nd pole.  Consider how it got from the 1st pole to the 2nd pole.  There could have been no other plates on either the 1st or 2nd pole because that would violate the rules.  So all other plates were stacked (in order) on the 3rd pole.  So, before the largest plate could even be moved to the 2nd pole, S(n-1) moves had to be made, where S(n-1) is the total number of moves required for the n-1 case. 

Similarly, when the largest plate is moved from the 2nd to the 3rd pole, there could have been no other plates on either the 2nd or the 3rd pole, so all the other plates had to be moved back to the 1st pole, again requiring S(n-1) moves.  After the largest plate is moved to the 3rd pole, the situation is identical to the starting situation for the n-1 case, so a final S(n-1) moves are required, leading to:

S(n) = S(n-1) + 1 + S(n-1) + 1 + S(n-1)
       = 3*S(n-1) + 2

and, given that S(1) = 2, a closed form expression of this solution is

S(n) = 2 * Sigma [x = 0 to n] 3^n-1, n > 0

just as Dej Mar found.

Posted by iamkobe on 2006-04-23 19:09:56