The strategy for the Hanoi Tower puzzle is quite simple. It is based on parity only. In an $n$-pieces puzzle, $2^n-1$ moves are sufficient to carry the whole pile from one pole to another one. My question is
Is there any mathematical (algebraic, logical, ...) structure associated with the Hanoi Tower puzzle? Does the optimal strategy translate into some mathematical result about this structure?
I searched "Tower of Hanoi" on arXiv (with 18 results at time of last edit):
A search on Wikipedia returned the Tower of Hanoi and Magnetic Tower of Hanoi. Also the Flag Tower of Hanoi.
People are interested in the graph of Tower of Hanoi positions, which seems to be related to the Sierpinski Gasket, the longest solution and Hamiltonian paths. (sources: wikimedia.org)
There seems to be a language (in the sense of automata theory) related to the Tower of Hanoi, and a fractal structure.
The language which I have usually seen it written in is that of self-similar groups, which are automorphisms of rooted trees. I'd say this mostly falls under the label of geometric group theory, and is quite useful in the study of dynamical systems. The language of finite automata is useful in understanding these groups though.
@John Mangual did a fairly thorough rundown of references. I might add V Nerkrashevych's book "Self-similar groups" or "From fractal groups to fractal sets" for the theory, though I forget off hand if the Hanoi towers game is in there. I'll give a quick overview of how the model works.
Let's stick with 3 pegs, and $n$-disks, it gets confusing with more pegs. The set of configurations of the game are represented by a string of $n$ $1$'s, $2$'s, or $3$'s. The $k$th entry of the string is which peg the $k$th smallest disk is on. This uniquely represents a configuration because larger disks need to be below smaller disks. So the goal becomes how many moves does it take to transform $11\cdots 1$ to $33\cdots 3$.
We represent moves by three actions $a_{12}$, $a_{23}$, $a_{13}$. Where $a_ij$ represents moving a disk from the $i$th peg to the $j$th peg or visa versa or doing nothing if there are no disks on the $i$th or $j$th peg. (again only one of these is a legal move because small disks sit on larger ones) If you look at the Schreier graph (undirected graph where two elements are connected if there a generator that transforms one into the other) generated by these group elements acting on the strings, you get the Sierpinski gasket-looking graph that John posted. The number of moves in the optimal strategy is the same as the diameter of this graph.
If you regard the collection of all strings of $1$'s, $2$'s, or $3$'s of all lengths as a rooted tree where two words are connected when one can be obtained from the other by appending an number to the right, i.e. $112$ is connected to $1121$. (we also need to add the "empty word," --- the word of length 0 so everything is connected). Then these $a_{ij}$ are automorphisms of this tree, and we can study the group they generate. The action of the group on the tree induces a relation on the boundary of the tree such the the boundary modulo the relation is the Sierpinski gasket with an induced self-covering. (in general a contracting self similar group induces a limiting dynamical system in this way)
I hope this helps!
Most mathematical models I know of are related to graphs (every vertex corresponds to a configuration of discs, and edges correspond to valid moves), and optimal strategies can be related to distances on these graphs.
There is a recent comprehensive monograph on the Tower of Hanoi and related puzzles (such as the Chinese Rings puzzle or the Tower of London). For the historically interested reader, there is also an in-depth account of the history of the puzzle and its mathematical treatment.
The fundamental group of the Menger Cube is an uncountable locally free and residually free group that contains the fundamental groups of all one-dimensional separable metric spaces as subgroups. It is known to frighten children and mathematicians alike. One can work within this group using a reduced path calculus; however, there is also an interesting word calculus (due to Hanspeter Fischer and Andreas Zastrow) that can be framed in terms of a variation of the Towers of Hanoi game. This is possible because the Menger cube may be realized as the inverse limit of finite groups each of which is the state-graph $X_n$ of a variation of the classical game using $n+1$ two-sided disks.
Hanspeter even created an ipad app that allows the user to move around within the approximating graphs $X_2$ (image below) while seeing the game state at the same time. It had dramatic whooshing and ringing sounds so naturally I spent too much time playing around with it.
Hanspeter Fischer, Andreas Zastrow, Word calculus in the fundamental group of the Menger curve, Fundamenta Mathematicae 235 (2016) 199-226. https://arxiv.org/abs/1310.7968
From the introduction of the cited paper regarding the details of the variation:
In our version of the Towers of Hanoi, the placement of the disks is restricted to within the well-known unique shortest solution of the classical puzzle, while we allow for backtracking within this solution and for the turning over of any disk that is in transition. We color the disks white on one side and black on the other. Then the state graph of this new “puzzle” is isomorphic to $X_n$, with edges corresponding to situations where all disks are on the board and vertices marking the moments when disks are in transition. The exponents of the edge labels ($x^{\pm 1}$ or $y^{\pm 1}$) indicate progress (“$+1$”) or regress (“$−1$”) in solving the classical puzzle (we add a game reset move when the classical puzzle is solved) and their base letters indicate whether the two disks to be lifted at the respective vertices of this edge are of matching (“$x$”) or mismatching (“$y$”) color. Hence, each edge-path through $X_n$ corresponds to a specific evolution of this game, as recorded by an observer of the movements of the $n + 1$ disks.
Our word calculus can be modeled by aligning an entire sequence of such puzzles with incrementally more disks into an inverse system, whose bonding functions between individual games simply consist of ignoring the smallest disk. Subsequently, every combinatorial notion featured in the description of the generalized Cayley graph has a mechanical interpretation in terms of this sequence of puzzles
