Tower of Ionah

The “Tower of Ionah” is the inversion (in a vertical direction) of the famous task of creating the “Tower of Hanoi“. This reversal also gave rise to the name “Ionah“, in that the sequence of the letters H, A, N, O, I changes into I, O, N, A, H by reading from right to left.

The story of the Tower of Ionah is thus also the story of the Tower of Hanoi (sometimes called the “Tower of Brahma” or the “End of the World Puzzle“; see below).

The Tower of Hanoi — and by extension the Tower of Ionah — was invented in 1883 by the French mathematician Francois Éduord Lucas (1842–1891). At first, it was simply a game with the name “M. Claus“.

In a simple form, the Tower of Ionah — as in the Maths Adventure Land — consists of five circular discs, one above the other, concentric in a recess. The Tower of Ionah includes two similar depressions (cf. Figure 1). The task of the game is to transfer the discs of the tower from one of the three recesses to a second one, following two rules:

You are only allowed to move one disc at a time.
You must not put a smaller disc on top of a larger one.

The third recess serves as an additional intermediate storage.

F. E. Lucas got the idea for this game as the Tower of Hanoi from the following Asian legend:

In the great temple of the Indian city of Benares (today: Varanasi), under the dome symbolising the centre of the world, rests a brass plate in which diamond needles are fixed, each a cubit (about 50–80cm) high and as strong as the body of a bee. At the creation of the world, God placed 64 discs of pure gold on one of the needles, the largest disc resting on the brass plate, and the rest, getting smaller and smaller, one on the other. This is the Tower of Brahma. Day and night the priests are ceaselessly busy, following the fixed and unchanging laws of Brahma, moving the discs from one diamond needle to another, the chief priest only being allowed to move one disc at a time, and in such a way that there is never a smaller disc under a larger one. As soon as all sixty-four discs have been transferred from the golden needle on which God placed them when he created the world to one of the other needles, the tower, along with the temple and all the Brahmins, will crumble to dust and the world will perish with a thunderclap, according to the legend.

And … the number of disc movements by the chief priest would be — following the legend — “at best“: $2^ {64} -1=18,446,744,073,709,551,615.$ .

If a disc movement required only one second, it would take the unimaginable period of 580 billion years to move the 64 golden discs. (According to current knowledge, the Big Bang, i.e. the creation of the universe, took place about 13.8 billion years ago).

In the Maths Adventure Land, the number of discs in the Tower of Ionah is not 64, but 5. As the mathematical reasoning below shows, the minimum number of movements of the five discs is $2^5-1=31$ to convert the Tower of Ionah into its previous shape (taking into account the rules above).

And now … the mathematics:

Let $n$ be the number of discs. Further, let $A$ denote the original tower with slices $S_1, S_2,\ldots , S_n$ (from “top” to “bottom”; $n\geq 1$ ), $B$ the “intermediate storage tower”, and $C$ the “target tower”.

The number of moves of the optimal solution (i.e. the minimum number of moves) is then $z_n=2^n-1$ . This can be proven by induction as follows:

For a single disc (i.e. $n=1$ ) this statement is certainly correct, because this only has to be moved from $A$ to $C$ ; the optimal sequence of moves then consists — as claimed — of a single move ( $z_1=2^1-1=1$ ).

So let’s say we are given $n\geq 2$ discs. In order to move the smallest slice $S_n$ (which is at the bottom at the beginning) from $A$ to $C$ , we first have to move the slices $S_1,\ldots,S_ {n-1}$ above it to $B$ . This costs us (at least) $2^ {n-1} -1$ moves for $n-1$ according to the induction assumption (the roles of $B$ and $C$ are reversed here). After we have completed this, we can flip the disk $S_n$ to $C$ and then, using the same procedure as before, flip the disks $S_1,\ldots,S_ {n-1}$ in (at least) $2^ {n-1} -1$ moves from $B$ to $C$ (here the roles of $A$ and $B$ are now reversed compared to the original problem). If we sum up all the moves, we thus obtain as claimed:

$z_n=z_ {n-1} +1+z_ {n-1} =2z_ {n-1} +1=2(2^ {n-1} -1)+1=2^n-1.$

In the same way, it is now possible to determine how often and on which moves each disc is moved in the optimal move sequence just described:

We claim that the disk $S_k$ is exactly in the moves

$1\cdot 2^k-2^ {k-1} ,2\cdot 2^k-2^ {k-1} ,\ldots,2^ {n-k} \cdot 2^k-2^ {k-1} ,$

so a total of $N_k=2^ {n-k}$ -times is moved (to test: $N_1+\cdots+N_n=2^ {n-1} +2^ {n-2} +\cdots+2+1=2^n-1=z_n$ gives the total number of all moves). Again we prove this with induction:

For $n=1$ the statement is correct, because the disk $S_1$ is then only moved in the move $1=2^1-2^ {1-1}$ .

So let’s assume $n\geq 2$ . Then, in the first $z_ {n-1} =2^ {n-1} -1$ moves, we run the game with the $n-1$ slices $S_1,\ldots,S_ {n-1}$ , with the roles of $B$ and $C$ reversed. So, the disk $S_k$ ( $1\leq k\leq n-1$ ) in this part of the game, according to the induction assumption, will be used exactly in the moves

$1\cdot 2^k-2^ {k-1} ,2\cdot 2^k-2^ {k-1} ,\ldots,2^ {n-1-k} \cdot 2^k-2^ {k-1}.$

This corresponds exactly to the first half of the moves of $S_k$ as listed above. Then the disk $S_n$ is moved in the move number $z_ {n-1} +1=2^ {n-1} =1\cdot 2^n-2^ {n-1}$ from $A$ to $C$ — as claimed. We then run our game again with the $n-1$ slices $S_1,\ldots,S_ {n-1}$ , with the roles of $A$ and $B$ now reversed. It follows that the disk $S_k$ ( $1\leq k\leq n-1$ ) continues in the moves

$2^{n-1}+1\cdot 2^k-2^{k-1}=(2^{n-1-k}+1)\cdot 2^k-2^{k-1},\ldots,2^{n-1}+2^{n-1-k}\cdot 2^k-2^{k-1}=2^{n-k}\cdot 2^k-2^{k-1},$

from which the claim follows.

With these considerations, it is now possible to determine at each point of the move sequence which disc must be moved next. Surprisingly, the resulting pattern corresponds exactly to counting in the binary system:If you want to find out which disc you have to move in the $m$ -th move according to the optimal procedure just described, write the number $m-1$ in binary and see up to which position the zeros and ones have to be “flipped” in the transition from $m-1$ to $m$ . For example, if $m=8$ , then $m-1=111$ in binary, so in order to count one more, you have to flip all the first four digits: $m=1000$ . So on the eighth move you have to move the fourth disc (if there are four discs; if not you are already done). For this interesting context, see also the videos [4] and [5] by YouTuber 3Blue1Brown.

As an algorithm

The above procedure can be summarised by the following algorithm:

Let

$\mathrm{Sol}[n,x,y]$ … be solution to a game that requires $n$ rings to be moved from the (circularly graded) shape $x$ (cf. Figure 1) to the corresponding shape $y$ ;
$\mathrm{not}(x, y)$ … the form that is different from the forms $x$ and $y$ (the “third” form);
$\mathrm{Sol} [1, x, y]$ … move a ring (directly) from $x$ to $y$ (already defined, but mentioned again here for better understanding).

Then you get the following recursive algorithm (in pseudo code) for the above task:

$\mathrm{Sol}[n,x,y]\coloneqq\{\mathrm{Sol}[n-1,x,\mathrm{not}(x,y)];\mathrm{Sol}[1,x,y];\mathrm{Sol}[n-1,\mathrm{not}(x,y),y]\}.$

Literature

[1] Gardner, M.: Mathematical Puzzles & Diversions, New York, 1959.

[2] van Delft, P., und Botermans, J.: Denkspiele der Welt, München, 1998.

[3] Link zum Applet

[4] https://www.youtube.com/watch?v=2SUvWfNJSsM

[5] https://www.youtube.com/watch?v=bdMfjfT0lKk