# 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!

1. ### qqwrefMember

7,832
17
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
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:

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. ### MaeLSTRoMMember

Jan 7, 2011
UK
WCA:
2011WALL02
MLSTRMRVLTN
Sounds pretty interesting. Are you planning to make a virtual version?

3. ### qqwrefMember

7,832
17
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
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. ### OwenMember

Nov 2, 2009
You are a genius and deserve the Noble prize in Awesome.

5. ### qqwrefMember

7,832
17
Dec 18, 2007
a <script> tag near you
WCA:
2006GOTT01
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}}$