qqwref
Member
- Joined
- Dec 18, 2007
- Messages
- 7,834
- Location
- a <script> tag near you
- WCA
- 2006GOTT01
- YouTube
- Visit Channel
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.
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.
