Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Tower of hanoi

  1. Mar 14, 2005 #1
    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

    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).
  2. jcsd
  3. Mar 15, 2005 #2
    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.
  4. Mar 16, 2005 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook