tower of hanoi

[msmith12]

There is a famous problem called the tower of hanoi in which you have n disks of increasing diameter, and three pegs. The object is to move them from one peg to another in such a way that no larger disk is on top of a smaller disk.

the number of moves is defined by

T(n)=2^{n}-1


A far more interesting and complicated problem, is, what is the minimum number of moves if you have 4 pegs instead of three?

Bonus: what is a formula in terms of
W(n) and T(n) --(where W(n) is the 4 peg number and T(n) is the number of 3 peg moves).

[BicycleTree]

Well, one strategy is to first move n-2 discs to one of the empty posts, then move the second-to-last disc to the other empty post, then move the last disc to the target post, then move the second-to-last disc to the target post, then move the n-2 discs to the target post. This gives a(n) = 3 + 2 * (a(n - 2)), with a(1) and a(2) being 1 and 3. Some experimentation (I don't know how to do it methodologically) shows that for odd n, a(n) = 2^((n-1)/2 + 2) - 3, and for even n, a(n) = 3 * (2^(n/2) - 1). Of course, I have no reason to believe this is the best strategy.

[BicycleTree]

Now I think it is the best strategy. To move the bottom disk you have to move somehow all the disks above it. To move the second-to-last-disk it must go onto a post that is already empty. The next step is clear, moving the last disk to target, and the step after that is equally clear, moving second-to-last disk to target.

I was thinking that maybe there would be some way to divide up the disks between the two spare posts in a way that might save future moves, but I guess not.