Hanoi Graphs and Sierpinski’s Triangle

The Tower of Hanoi is a famous mathematical puzzle. A set of disks of different sizes are stacked like a cone on one of three rods, and the challenge is to move them onto another rod while respecting strict constraints:

Only one disk can be moved at a time.
No disk can be placed upon a smaller one.

Tower of Hanoi [image Wikimedia Commons].

Many years ago, I read in Ripley’s Believe It or Not column that, in a Buddhist temple in India, there is a large room with three stout pillars on which 64 golden disks are stacked. A team of monks work tirelessly, transferring these disks between the three pillars. With one movement each second, the time required to solve the puzzle is about 585 billion years, at which time the world will either end, or enter another cycle.

However, Ripley was not always a reliable source: in fact, the puzzle was invented in 1883 by the French mathematician Édouard Lucas. The minimum number of moves required to solve the puzzle with ${n}$ disks is ${2^n-1}$ , the ${n}$ -th Mersenne number. There are algorithms to ensure a solution in the minimum number of moves (see Wikipedia page referenced below).

Graphical Representation

There is a simple graphical representation of all the legal states of the puzzle. We number the disks from ${1}$ to ${n}$ in order of increasing size. Then the position at any time can be given by a string of numbers ${d_1 d_2 \dots d_n}$ , where ${d_{k}\in\{1,2,3\}}$ is the number of the post on which the ${k}$ -th disk rests. Since exactly one disk changes position at each stage, only one of these numbers changes when a move is made.

We have ${3^n}$ possible strings, but not all of these correspond to legal positions (for which no larger disk rests on a smaller one). Each legal position is a node of the graph, and we link every pair of nodes that differ by a single move.

The simplest case, with just one disk, is shown in the figure here. Each position, or node, of the graph is represented by a small triangle and there are legal moves from any triangle to other triangles that touch it. In this trivial case, graph ${H_1}$ , a single move ( ${2^1-1}$ ), suffices to transfer the disk from post 1 to either post 2 or post 3.

With two disks, there are 9 legal positions. For example, disk 1 (smaller) on post 2 and Hanoi-02 disk 2 (the larger) on post 3 is represented by the string 23. We can get from position 11 to either 22 or 33 in ${2^2-1=3}$ moves, as seen in the diagram of ${H_2}$ shown here.

Diagrams of the Hanoi graphs ${H_3}$ for ${n=3}$ and ${H_4}$ for ${n=4}$ can be found in the article by Hinz and Freiberger (2014). In general ${H_{n+1}}$ comprises three copies of ${H_n}$ linked at their extremities. For increasing ${n}$ , a pattern becomes clear: the shape of the graph increasingly resembles the approximations to the Sierpinski triangle. This is formed by starting with an equilateral triangle, dividing it into four identical pieces, and removing the central piece (an inverted triangle).

Sierpinski Triangle and Pascal’s Triangle

The Sierpinski Triangle may be formed in a manner analogous to the Cantor set. We start with the entire (solid) equilateral triangle. At each stage, we divide each solid triangular portion into four similar triangles and remove the central one. This procedure is continued indefinitely. Since, at each stage, the area is reduced by a factor ${\frac{3}{4}}$ , the remaining area must converge to zero. Moreover, taking the bottom-left section (one third of the total) and doubling its length in each direction gives us three copies of the bottom-left section, so the fractal dimension d is given by ${2^d = 3}$ or ${d = \log3/\log2 \approx1.585}$ .

Sierpinski triangle construction by trisection.

There is yet another way to generate the Sierpinski triangle. The even entries in Pascal’s Triangle are arranged in triangular groups, like the white portions of the figure above. If all even numbers are eliminated, what remains in the limit has the structure of the Sierpinski triangle. The figure below is obtained by plotting a small triangle at each of the odd entries for the first 64 rows of Pascal’s Triangle. It also illustrates the structure of the Hanoi graph ${H_6}$ , which has ${3^6=729}$ nodes.

Sierpinski triangle constructed by keeping only odd entries in first 64 rows of Pascal’s Triangle. The structure is the same as for $H_6$.

Sources

${\bullet}$ Hinz, A. M. and Marianne Freiberger, 2014: The Tower of Hanoi: where Mathematics meets Psychology. Pp 84–88 in 50 Visions of Mathematics, Ed. Sam Parc, 2014: Oxford Univ. Press, 198pp. ISBN: 978-0-1987-0181-1.

${\bullet}$ The Chaos Game. Blog post at https://thatsmaths.com/2014/05/22/the-chaos-game/

${\bullet}$ Wikipedia article Tower of Hanoi: https://en.wikipedia.org/wiki/Tower_of_Hanoi

Related

Published by thatsmaths