# 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.

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”: .

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 , in order to convert the tower of Ionah into its previous shape (considering the above rules).

#### And now … the mathematics of it:

Let be the number of slices. Further, let denote the original tower with slices (from “top” to “bottom”; ), the “intermediate tower”, and the “target tower”.

The number of moves of the optimal solution (i.e., the minimum number of moves) is then . This can be proved by induction as follows:

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

So suppose we are given slices. To move the smallest slice (the one at the bottom at the beginning) from to , we must first move the slices above it to . This costs us (at least) moves according to the induction assumption for (the roles of and are reversed here). After completing this, we can move the disk to and then, using the same procedure as before, move the disks from to in (at least) moves (here the roles of and are now reversed compared to the original problem). If we sum up all the moves, we thus obtain as claimed: 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 is moved exactly in the moves so a total of times is moved (to test: gives the total number of all moves). Again, we prove this by induction:

For the statement is correct, because the disk is then moved only in move .

So let us assume . Then in the first moves we run the game with the disks with the roles of and reversed. Thus, in this part of the game, the disk ( ) is moved exactly in the moves by induction assumption.

moves. This corresponds exactly to the first half of the moves of as listed above. Then the disk is moved from to in move number — as claimed. We then run our game again with the disks , with the roles of and now reversed. It follows that the disk ( ) continues in the moves 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 -th move according to the opimal procedure just described, write the number in the binary system and see up to which place the zeros and ones have to be “flipped” in the transition from to . For example, if , then in binary, so in order to count one more, you have to flip all the first four digits: . 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  and  by YouTuber 3Blue1Brown.

#### As algorithm

The above procedure can be summarized by the following algorithm:

Let

• … Solution of a game that requires to move rings from the (circularly graded) shape (cf. Figure 1) to the corresponding shape ;
• … the form different from the forms and (the “third” form);
• … move a ring (directly) from to (already defined, but mentioned here again for better understanding).

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

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

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