1. Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 30,000+ people from around the world today!
    Dismiss Notice

Extension to the Tower of Hanoi

Discussion in 'Off-Topic Discussion' started by qqwref, Jan 24, 2012.

  1. qqwref

    qqwref Member

    7,830
    39
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    I didn't know where else to put this, but I'm sure some people here will find this interesting. Hopefully this is actually new and not an obvious thing that I somehow couldn't find on Google.

    So, you're probably all familiar with the Tower of Hanoi problem. You have three pegs, and $$n$$ disks of different sizes on one of the pegs, arranged with the largest disks on the bottom. The goal is to move all the disks to a different peg; the rules are that (a) you can only move one disk at a time (from one peg to another peg), and (b) you can't place a disk on top of a smaller disk. The problem is not too difficult to solve if you are just trying to finish it, but the mathematically interesting thing is that it requires $$O(2^n)$$ moves - roughly doubling for every new disk you add. The reason for this is that, to move $$n$$ disks, you must first move the smallest $$n-1$$ disks to another peg, then move the biggest disk, and finally move the rest of the disks a second time.

    For a while I've been casually trying to think of a way to extend this to create puzzles which require $$O(k^n)$$ moves (for $$n$$ disks, and for a $$k$$ as large as we want). I think I've got an idea which will let us do this. Here is a rough picture of the idea, for a small case:
    [​IMG]
    So, here's what's going on here. Choose some number $$j$$. Instead of 3 pegs you have $$2j+1$$ pegs, and instead of disks that cover one peg, they cover $$j$$ adjacent pegs. The trick is that the only way to move a disk is to move all of the smaller disks to $$j$$ of the other $$j+1$$ pegs - and, even then, this will only allow you to move the remaining disk clockwise or counterclockwise by one peg.

    Figuring out the number of moves is a little trickier than in the normal 3-peg version, but at least we know that we can only move the biggest disk if all of the other disks are in a pile. To move a pile of $$n$$ disks by one space, we need to (1) move $$n-1$$ disks by $$j$$ spaces, (2) move the biggest disk, and then (3) move $$n-1$$ disks by $$j$$ spaces again. To move a pile of $$n$$ disks by $$k$$ spaces, though, we need to (1) move $$n-1$$ disks by $$j$$ spaces, (2) repeat (move the biggest disk, then move $$n-1$$ disks one space) $$k-1$$ times, (3) move the biggest disk one last time, and then (4) move $$n-1$$ disks by $$j$$ spaces again to finish. Only moves of 1 and $$j$$ spaces seem to be important here, so if we write those as $$m_1(n)$$ and $$m_j(n)$$ the recursion looks like this:
    $$m_1(n) = 2 m_j(n-1) + 1$$
    $$m_j(n) = 2 m_j(n-1) + (j-1) m_1(n-1) + j$$
    Or, just in terms of the 1-move numbers:
    $$m_1(n) = 2 m_1(n-1) + (2j-2) m_1(n-2) + 2j-1$$

    Anyway, it looks like the $$k$$ constant (the number for which $$m_1(n)$$ grows like $$k^n$$) works out to $$1 + \sqrt{2j-1}$$. So that's pretty interesting, and we can definitely get $$k$$ as large as we like by choosing a sufficiently high $$j$$. In fact, we can set $$k$$ to be any even integer: for instance, let $$j=41$$, and then the sequence $$m_1(n)$$ grows as fast as $$10^n$$. Of course, boards with 83 pegs and disks with 41 holes are not particularly nice to play with, but seeing as the 5-disk puzzle takes 14,751 moves to just move the disks one space over, I don't think a lot of people would complain.

    Incidentally, if you don't like the idea of disks spanning multiple pegs, you can get the same effect by using 1-peg disks and adding the rule that you cannot put a disk onto a peg if a smaller disk is on that peg or one of the next $$j-1$$ pegs in either direction.
     
  2. MaeLSTRoM

    MaeLSTRoM Member

    1,862
    4
    Jan 7, 2011
    UK
    WCA:
    2011WALL02
    YouTube:
    MLSTRMRVLTN
    Sounds pretty interesting. Are you planning to make a virtual version?
     
  3. qqwref

    qqwref Member

    7,830
    39
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Hm, not really. I guess I could, but I'm not really sure how - I imagine the controls would be pretty finicky, and I'm not really sure how I'd display it...
     
  4. Owen

    Owen Member

    1,141
    4
    Nov 2, 2009
    You are a genius and deserve the Noble prize in Awesome.
     
  5. qqwref

    qqwref Member

    7,830
    39
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Alright guys, I made a sim :tu Try it here:
    http://mzrg.com/js/hanoi/

    I basically was thinking about how to expand the problem while keeping the restricted feel of the original one (only really one way to move stuff around) and I randomly thought of the idea of disks that would cover more than one peg, and of just barely having enough pegs to move those disks around. I initially had a wrong idea of how the math would turn out (since I didn't realize you could take shortcuts when moving a group of disks more than one space at a time) but the idea turned out to be what I wanted anyway.


    PS: Wolfram Alpha gives the following closed form for $$m_1$$:
    $$m_1(n) = -1 + \frac{(1+\sqrt{2j-1})^n - (1-\sqrt{2j-1})^n}{\sqrt{2j-1}}$$
     

Share This Page