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
re: Solution by iamkobe)
Dej Mar and iamkobe are correct, and I did not read the question thoroughly.
The correct solution is f(n) = (3^n)-1.
My initial post only considered moving the plates to the middle pole. To get them to the furthest pole takes twice as many moves. Thus (3^n)-1 vice ((3^n)-1)/2.
|
|
Posted by Leming
on 2006-04-23 19:37:12 |
re(2): Solution - R.T.Q.
