# Mathematical model for Hanoi Towers

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?

-
There's an interesting piece in: Stewart, I. (1995). Four encounters with sierpińriski’s gasket. The Mathematical Intelligencer, 17(1), 52-64. In particular, see Encounter 3. (Paywall, I think: link.springer.com/article/10.1007%2FBF03024718) – Benjamin Dickman May 27 '13 at 15:50
Take also a look at mathematik.uni-muenchen.de/~hinz/hanoi.html – j.p. May 27 '13 at 16:57
If you have access to Math Reviews online, and you type in tower* of Hanoi, you get 189 hits. – Gerry Myerson May 27 '13 at 23:56

I searched "Tower of Hanoi" on arXiv:

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.

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. (it ends up being $(\Bbb Z/ 2\Bbb Z)^{*3}$, since each element is idempotent but does not commute with the others). 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.

-