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 oneonone 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 piledup 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 3case 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^n1 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 3disk 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 clockwise, that after the 2nd move disk 2 moves every 4 configurations counterclockwise, 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.