The puzzle to predict the end of the universe: what the Tower of Hanoi is and how to solve it

There Hanoi tower is a puzzle created by the French mathematician Édouard Lucas d’Amiens and presented for the first time in 1883. The game consists of three stakes and from a series of discs of different sizes that they must be move respecting some precise rules.

When the puzzle was released, it was accompanied by a story designed to make it more fascinating. According to this legendthe game would be the simplified version of the “Sacred Tower of Brahma”, a tower made up of 64 gold records which must be moved following the same rules as the puzzle and on which the temple brahmins work day and night, moving one disk per second. The legend, of which there are many different versions, tells that when the last disk has been moved, the universe will come to its end.

Of course it is one invented story to accompany the game, without any basis in truth, but this idea brings with it an interesting question: how long would it really take to solve a tower with 64 discs if it could be done one move per second?

Let’s see how to play the Tower of Hanoi, how to solve it and how many moves are needed to solve the “Sacred Tower of Brahma” tower and reach the end of the universe.

How to play Hanoi Tower

The Hanoi Tower consists of three stakes and from some discs (generally 8) of different sizes, drilled in the center so they can be inserted onto the posts. At the start of the game all discs are on the first post, stacked from largest at the bottom to smallest at the top.

The goal And move the entire tower to the last postrespecting some fundamental rules:

• it can be moved only one disc at a time;
• each move consists of moving a disc from one rod to another. It is not possible, for example, to remove a disc and temporarily place it outside the auctions;
• Not can you ever place a larger disk on top of one smaller. The disks must therefore always remain ordered from the largest at the bottom to the smallest at the top.

How to solve the Tower of Hanoi and how many moves it takes

To understand how the Tower of Hanoi is solved and how many moves are necessary, let’s start with the simplest possible case: a tower made up of a single disk.

Only one disc

If we have only one discthe solution is immediate. Just move the disc from the first to the last rod and the puzzle is solved. It’s useful just one move.

Two discs

With two discs the situation is still simple, but we have to start thinking a little. If we immediately moved the smaller disc to the last post, then we couldn’t put the green one on it (because it’s bigger) and we would waste moves.

The correct sequence is therefore:

• we move the smaller disk onto the central rod;
• we move the largest disk to the final rod;
• we finally move the smaller disk onto the final rod.

In this way we recreate the tower on the last rod respecting all the rules. For two discstherefore, they are useful three moves.

Three discs

With three discs the tower of Hanoi begins to require a real strategy. To be able to recreate the tower in the last post on the right, we must ensure that the largest disk, which is located at the base of the tower, is free to move on the right rod. To do this, we need to temporarily move the two smaller disks onto the central pole.

We can proceed like this:

• we move the smaller disk to the right rod;
• we move the intermediate disk onto the central rod;
• we move the smaller disk above the intermediate one.

As before, to move two discs onto any post, we used 3 moves. At this point, the two smaller disks are on the central rod and the larger disk is free to move to the right rod, using another move. Now, with 3 more moves, we also transfer the other two discs to the last rod, recreating the tower.

The move count is therefore:

• 3 moves to move the two smaller discs onto the central post,
• 1 move to move the larger disk onto the right rod,
• other 3 moves to move the two smaller disks again and complete the tower.

In total they are needed 7 moves to move 3 discs.

The general solution

If we now try to think about a tower with 4 discsthe mechanism becomes clearer:

• to move the largest disk we must first move the three smaller disks on the central rod. As we have seen, it takes 7 moves to move 3 discs.
• At this point we can move the largest disk onto the final rod with a single move.
• Finally we have to move the three discs onto the final pole again, which requires another 7 moves.

In total:

7 + 1 + 7 = 15 moves

What if we wanted to move 5 discs? First we would use 15 moves to move 4 pucks to the center post, then we would use one move to move the larger puck to the right post and then another 15 moves to respond the smaller pucks to the end post.

So we should use 15 +1 +15 = 31 moves.

And for 6 discs? For 8? For 64? The reasoning is always the same: to move a tower of X discs we have to

• move the first ones X−1 discs on an intermediate auction
• move the larger disk
• move them again X−1 discs above him

This type of solution, in which to understand what to do we have to look at the solution of the previous case, is called recursive solutions and, precisely because the Tower of Hanoi has a solution of this type, it is often used as an example during computer science lessons to learn how to write recursive algorithms.

In how many seconds will the universe end

Another, slightly more compact, way to describe how many moves it will take to solve the Tower of Hanoi is the formula:

number of moves = 2^{(number of disks)} – 1

In fact, with two discs, we need 2² – 1 = 4 – 1 = 3 moves, with 3 discs you need 2³ – 1= 8 – 1 = 7, with 4 you need 2⁴ – 1 = 15 and so on.

This formula is very useful for calculating how many moves we need to solve the Tower of Brahma, made up of 64 golden discs, without having to calculate all the previous steps. Applying the formula we have that 2 are needed⁶⁴ − 1 move. If we imagine that the monks manage to make one move per second, the universe will end 18,446,744,073,709,551,615 seconds after the start of the game, that is, approximately 585 billion years. In short, nothing to worry about.