A boring solution to the Tower of Hanoi

Yesterday night I was trying to figure out how to get my son interested into some activity to be done with me, when I recalled buying online a puzzle called Tower of Hanoi. We spent a quarter of an hour playing one-on-one with invented rules, which didn’t work out very well. Then we went to Wikipedia to take a look at what’s the whole point with it (but without looking at the solution, ca va sans dire). And the point is you have three poles and a number of disks (in my case 9) of different sizes, initially piled-up from larger to smaller on one pole (let’s take only 3 to visualize):

1 0 0
2 0 0
3 0 0

“0” means “empty space”. The scope is, moving only one disk at a time in such a way that smaller disks always sit on top of larger disks, you have to rebuild the tower on another pole. In the 3-case it’s easy (vertical bars separate configurations):

1 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 1 0
2 0 0 | 2 0 0 | 0 0 0 | 0 0 1 | 0 0 1 | 0 0 0 | 0 2 0 | 0 2 0
3 0 0 | 3 1 0 | 3 1 2 | 3 0 2 | 0 3 2 | 1 3 2 | 1 3 0 | 0 3 0

We managed to spend some another fifteen minutes together, then he was bored and I was captured, I let him to his room so that I could be alone with it. I had managed to pile up a few disks, and the problem was obviously going to be based on some iterative procedure. Somehow as my hands were shuffling around I noticed that I was almost always making the same move with one of them, and I came up with this simple solution that makes the whole puzzle completely boring once you know it [and which turns out to be identical to the Wikipedia solution, I just took a look at it…]. It’s made up of two moves, to be iterated until you reach your final configuration (spoiler alert!):

    • Move the smallest disk (that of radius 1) to the next pole (mod 3)
    • Do the only allowed move on the other two poles.

You can check by yourself that this is what’s going on in the above scheme. I tried several times and found that with 2 rings I get 4 configurations, with 3 I get 8, with 4 I get 16 and you got the point, it takes 2^n-1 transitions to get to the final state. Which is exactly what other methods described in the Wikipedia page attain.

Now the question is why does this solution work. I don’t have a mathematical proof yet, can’t waste my time on these things really. But let’s collect a few simple facts. First thing, notice that if I add another disk, I get:

1 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 |
2 0 0 | 2 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 1 0 |
3 0 0 | 3 0 0 | 3 0 0 | 3 0 1 | 0 0 1 | 1 0 0 | 1 2 0 | 0 2 0 |
4 0 0 | 4 1 0 | 4 1 2 | 4 0 2 | 4 3 2 | 4 3 2 | 4 3 0 | 4 3 0 |

0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 1
0 1 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0 0 2 | 0 0 2
0 2 0 | 0 2 1 | 0 0 1 | 1 0 0 | 1 0 3 | 0 0 3 | 0 0 3 | 0 0 3
0 3 4 | 0 3 4 | 2 3 4 | 2 3 4 | 2 0 4 | 2 1 4 | 0 1 4 | 0 0 4

But this is just twice the 3-disk pattern above, once on top of of disk 4 on the first column, and once on top of disk 4 on the third. Notice that, after the 1st move, disk 1 moves every two configurations clock-wise, that after the 2nd move disk 2 moves every 4 configurations counter-clockwise, and that after the 4th move disk 3 moves every 8 configurations clockwise, and that after the 8th move disk 4 moves every 16 configurations counterclockwise. To build a proof, one should show that the configurations reached this way are always feasible (no larger disk on a smaller one) and “ergodic”, meaning that they span all of the possible configurations, until they eventually reach the desired one.

I leave this to you as homework.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s