The Tower of Hanoi: Where maths meets psychology

Mathematicians and psychologists don't cross paths that often and when they do you wouldn't expect it to involve an (apparently) unassuming puzzle like the Tower of Hanoi. Yet, the puzzle holds fascination in both fields. In psychology it helps to assess someone's cognitive abilities. In maths it displays a wealth of beautiful features and leads you straight to surprisingly tricky questions that still haven't been answered.

The rules of the game are straight-forward. You've got three pegs and a number of discs (eight of them in the original version), stacked up on one of the pegs in order of size, with the biggest disc at the bottom. Your task is to transfer the whole tower onto a different peg, disc by disc, but you're not allowed to ever place a larger disc onto a smaller one.

The mathematician Andreas M. Hinz is someone who has looked at the game from both the mathematical and the psychological angle. He is about to publish a book about the Tower and he has collaborated with psychologists to produce a new tool for assessing patients. He explains that it's the game's simplicity that makes it so interesting to psychologists. "The game is easy to explain and you can watch people think," he says. "[Test persons] make the moves in front of the experimenter and so one can see every step, every single strategy the person tries. That's why psychologists like it so much."

The game lends itself particularly to assessing people's ability to plan ahead and to chop a task into more digestible chunks: to move the whole tower you first need to move the tip of it, and the same rules apply to this sub-problem. It's also easy to vary the problem: you can add more discs or you can stipulate new starting and final configurations that don't have all the discs stacked up on one peg. It turns out that both of these features, the game's recursive nature and its variability, lead to some very interesting maths too.

The game plan

The best way to see the scope of the game is to draw a network, or graph, that displays all the possible configurations and moves. Suppose we play the game with three discs and three pegs. Label the discs 1, 2 and 3 with 1 being the smallest one and 3 the largest one. Also label the pegs 1, 2 and 3. Now suppose discs 1 and 3 are on peg 1 and disc 2 is on peg 3. You can encode this situation using the triple (1,3,1). The positions in the triple correspond to the discs and the value in a position tells you which peg the corresponding disc is sitting on. There's no confusion about the order in which discs sit on a given peg because we know that they have to be arranged in order of size. So all the legal configurations of discs can be encoded unambiguously in triples of numbers.

Connecting the dots.

Now for each triple draw a dot on a piece of paper. Connect two dots if a single move can get you from one of them to the other. For example, the dot corresponding to the starting position (1,1,1) (all discs on peg 1) is joined to the dots corresponding to positions (2,1,1) (disc 1 on peg 2 and the rest still on peg 1) and (3,1,1) (disc 1 on peg 3 and the rest still on peg 1). Altogether there are 3³=27 possible positions. These can be arranged to give you the following graph:

The Hanoi graph H₃.

This object is called a Hanoi graph and it's denoted by H₃. The subscript 3 indicates that we are looking at a game with three discs.

The Hanoi graph makes it easy to keep track of how someone is playing the game. "The main reasons why psychologists were so enthusiastic about the Hanoi graph is that you can draw the [sequence of moves] the test person has followed on it," explains Hinz. "You can easily see whether the person has made the best moves or, if not, where they had problems, at which stages they were thinking for a long time, etc. So you can get a lot of information from the result of a test on one person, or even a group if you overlay their traces on the graph."

Playing the game with three discs is easy, so what can we say about the game with 4, 5, 6 or any number n of discs? In terms of the graphs a very pretty picture emerges: the Hanoi graph H₄ for the four-disc version of the game consists of three copies of H₃ each connected to each of the other two by exactly one edge.

 

The Hanoi graph H₄ consists of three copies of H₃. Click here for a larger version of the image.

Similarly, H₅ consists of three copies of H₄, H₆ consists of three copies of H₅ and so on. This is due to the recursive nature of the game: if you ignore the biggest disc, the n+1-disc version of the puzzle turns into the n-disc version. Say for example that you have four discs and that the biggest one, disc 4, is sitting on peg 1. Any legal move you can make with the remaining three discs is also a legal move in the three-disc version you get by pretending disc 4 isn't there. So if you look at the nodes in H₄ that correspond to disc 4 sitting on peg 1 (these are the nodes whose labels end in a 1) what you see is a copy of H₃. Similarly, you get a copy of H₃ for the nodes which have disc 4 sitting on peg 2 and another copy for the nodes with disc 4 sitting on peg 3.
How do you move between these copies? You can only ever move disc 4 when the other three discs are all stacked up on one of the other two pegs. There are two nodes representing this situation in each copy of H₃ (one for each of the other two pegs the remaining discs can be stacked up on) and from each you get an edge to one of the other two copies (representing the move of disc 4 ). So the copies are linked pairwise by one edge. The same argument works to show that H_n+1 consists of three copies of H_n for any number n of discs.

Andreas M. Hinz introducing his book, The Tower of Hanoi — Myths and Maths, at the European Congress of Mathematics in Krakow in July 2012.

Adding ever more discs to the puzzle doesn't actually make it much more difficult once you have cracked the method for solving it. But things change when you stipulate that the game should start and end not with all discs sitting in a tower on one peg, but with different arrangements of discs. "In this case the puzzle becomes pretty hard," says Hinz. "Psychologists use this variation in tests, but its structure was not very well understood by them. [We helped them] with this mathematical model of a graph, which can be analysed mathematically."
For example, using graphs you can see immediately that no matter which starting and finishing configurations you stipulate, it is always possible to solve the puzzle, no matter how many discs there are. This is because, as you can easily deduce from the recursive structure, each Hanoi graph H_n is connected: there's a path between any two of its nodes.

But what about optimal solutions, those that require the smallest number of moves? For the usual initial and final configurations, with all discs on one peg, you can show that the smallest number of moves required is And this is the worst case: for arbitrary starting and final configurations the smallest number of moves is at most You can prove this using mathematical induction: you first show that it is true for some initial value of , say and then you show that if it is true for then it is also true for . (Try to work this out for yourself, or see the proof here.)

Triangle connections

For mathematicians the possibility of adding discs poses another intriguing question. What can we say about the graph for a hypothetical game with an infinite number of discs? Well, have a look at the image below.

Sierpiński's triangle.

This is Sierpiński's triangle, which you get from another infinite process. You start with a (filled-in) equilateral triangle and remove the middle (up-side down) triangle you get from connecting the mid-points of the three sides (you only remove the inside of that triangle, leaving behind the sides). You're left with three equilateral triangles and again remove the centre triangle from each of them, leaving you with 9 triangles. Keep going, always removing centre triangles from what's left, ad infinitum. The object you get in the limit is Sierpiński's triangle.
Sierpiński’s triangle is one of the most popular examples of a fractal. It is self-similar: if you zoom in on what’s left of any given triangle, no matter how tiny, what you see is exactly the same as the whole picture. It also lives in a strange world in-between dimensions: it is "more" than a smooth one-dimensional curve, yet its area is zero so it’s not a two-dimensional object either. Mathematicians have generalised the notion of dimension to capture the nature of such complex objects, and in this generalised setting the Sierpiński’s triangle has dimension
As you add more and more discs to the Tower of Hanoi game, the corresponding graph, suitably rescaled, starts to look more and more like Sierpiński's triangle. And the object you get in the limit as n tends to infinity has exactly the same structure as Sierpiński's triangle.
There is an equally intriguing connection to another triangle beloved by mathematicians: Pascal's triangle. (We won't define it here, if you have not come across it, there is a good explanation here.) If you take the first 2ⁿ rows of Pascal's triangle and connect odd numbers that lie next to each other, either horizontally or diagonally, by a line, then the graph you get has exactly the same structure as the Hanoi graph H_n.

The first eight rows of Pascal's triangle with adjacent odd entries connected.

These kind of connections aren't only beautiful, they are also useful. Results that are hard to prove for one of these objects may be easier to prove for another and can then be transferred. For example, suppose you travel around Sierpiński's triangle, but without ever leaving the fractal itself. What's the average distance between two points? No-one had been able to answer this question until Hinz calculated it using Hanoi graphs: it's 466/885 (assuming that the side-length of the initial triangle in the construction of Sierpiński's triangle is 1).

Adding pegs

So much for adding discs, but what happens if you introduce another peg? The game itself becomes easier because you have more scope for moving discs around. But the graphs also lose their neat structure. There are now more configurations of discs that allow you to move the largest disc — the smaller ones no longer need to be stacked up on one peg. This means that the chunk of the graph that has the largest disc sitting on peg 1, say, and the chunk that has it sitting on peg 2 are connected by more edges than just one. This makes the graphs more complex. "For four pegs the graphs are usually not planar anymore," explains Hinz. "This means you cannot draw them on a sheet of paper [without the edges crossing]. You need three dimensions for that. We still do not understand these graphs very well because they are strongly intertwined."

Hinz with the co-authors of his book. From left to right: Ciril Petr, Andreas M. Hinz, Sandi Klavžar, and Uros Milutinović.

This complexity means that seemingly simple questions can be surprisingly hard to solve. For example, nobody knows how long the shortest solution is for the classical finishing and starting configurations. There are strategies for solving the multi-peg puzzle and the notorious Frame-Stewart conjecture says that these are optimal. But although the conjecture is over 70 years old the problem is still undecided. It has been proved, with the aid of computers, only for games with up to 30 discs.
Hinz is a mathematical physicist by trade, but his fascination with the Tower of Hanoi has been an interesting diversion. "The collaborations with people from graph theory, who are my co-authors on the book, and with psychologists have been fascinating," he says. The assessment tool he produced with psychologists is now being used, for example to test people with dementia or who have suffered stroke, to see which areas of the brain have been impaired.
But it's not all about usefulness. "The mathematician Ian Stewart once said that people are intrigued by maths because it is fun, it is beautiful and it is useful," says Hinz. "But I would like to add a fourth point: people like maths because it is surprising." As a mathematical object the Tower of Hanoi certainly fits the bill on all four points.

plus