Extension to the Tower of Hanoi

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

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. qqwref

    qqwref Member

    7,833
    22
    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
    1
    Jan 7, 2011
    UK
    WCA:
    2011WALL02
    YouTube:
    MLSTRMRVLTN
    Sounds pretty interesting. Are you planning to make a virtual version?
     
  3. qqwref

    qqwref Member

    7,833
    22
    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,139
    0
    Nov 2, 2009
    You are a genius and deserve the Noble prize in Awesome.
     
  5. qqwref

    qqwref Member

    7,833
    22
    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