Tower of Ionah

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

Figure 1

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

The Tower of Hanoi — and thus the Tower of Ionah — was invented in 1883 by the French mathematician Francois Éduord Lucas (1842–1891). It was initially simply a game called “M. Claus.”

In a simple form, the Tower of Ionah — as in MATHEMATICS ADVENTURE LAND — consists of five circular discs, one above the other, concentric in a depression. Two similar depressions belong to the Tower of Ionah (cf. Figure 1). The task of the game is to transfer the disks of the tower from one of the three depressions to a second one, following two rules:

  • You are only allowed to flip one disc at a time.
  • You can’t put a smaller one 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 symbolizing the center of the world, rests a brass plate in which diamond needles are fixed, each one a cubit (about 50–80cm) high and 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, with 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 engaged, following the fixed and unchanging laws of Brahma, in transferring the discs from one diamond needle to another, the chief priest being allowed to transfer only 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 will have been transferred from the golden needle, on which God placed them at his creation of the world, to one of the other needles, the tower together with the temple and all Brahmins will crumble to dust, and the world will perish with a thunderclap.

And … the number of disc movements by the supreme priest would be — following the legend — “in the most favorable case”:

    \[2^{64}-1=18,446,744,073,709,551,615.\]

.

If a disk movement would require only one second, the moving of the 64 golden disks lasted the unimaginable period of 580 billion years. (The big bang, thus the emergence of the universe, took place according to today’s knowledge approx. 13.8 billion years ago!)

In the MATHEMATICS ADVENTURE LAND the number of the disks of the tower of Ionah is not 64, but 5. As the mathematical consideration following below shows, the minimum number of the movements of the five disks is 2^5-1=31, in order to convert the tower of Ionah into its previous shape (considering the above rules).


And now … the mathematics of it:

Let n be the number of slices. 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 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 proved by induction as follows:

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

So suppose we are given n\geq 2 slices. To move the smallest slice S_n (the one at the bottom at the beginning) from A to C, we must first move the slices S_1,\ldots,S_{n-1} above it to B. This costs us (at least) 2^{n-1}-1 moves according to the induction assumption for n-1 (the roles of B and C are reversed here). After completing this, we can move the disk S_n to C and then, using the same procedure as before, move the disks S_1,\ldots,S_{n-1} from B to C in (at least) 2^{n-1}-1 moves (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, we can now determine how many times and on which moves each disk is moved in the optimal sequence of moves just described:

We claim that the disk S_k is moved 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}+\cdot+2+1=2^n-1=z_n gives the total number of all moves). Again, we prove this by induction:

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

So let us assume n\geq 2. Then in the first z_{n-1}=2^{n-1}-1 moves we run the game with the n-1 disks S_1,\ldots,S_{n-1} with the roles of B and C reversed. Thus, in this part of the game, the disk S_k (1\leq k\leq n-1) is moved 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}\]

by induction assumption.

moves. This corresponds exactly to the first half of the moves of S_k as listed above. Then the disk S_n is moved from A to C in move number z_{n-1}+1=2^{n-1}=1\cdot 2^n-2^{n-1} — as claimed. We then run our game again with the n-1 disks 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}\]

is moved, from which the assertion follows.

With these considerations, it is now possible to determine at each point in the sequence of moves which disk must be moved next. Surprisingly, the resulting pattern corresponds exactly to counting in the binary system: If you want to find out which disk you have to move in the m-th move according to the opimal procedure just described, write the number m-1 in the binary system and see up to which place 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 in the eighth move you have to move the fourth disk (if there are four disks; if not you are already done). For this interesting context, see also the videos [4] and [5] by YouTuber 3Blue1Brown.


As algorithm

The above procedure can be summarized by the following algorithm:

Let

  • \mathrm{Sol}[n,x,y] … Solution of a game that requires to move n rings from the (circularly graded) shape x (cf. Figure 1) to the corresponding shape y;
  • \mathrm{not}(x, y) … the form 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 here again for better understanding).

Then, for the above task, we obtain the following recursive algorithm (in pseudocode):

    \[\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