Comments

The towers of Hanoi

The towers of Hanoi

Legend has it that in the great temple of Varanasi, below the dome that marks the center of the world, lies a bronze base on which three diamond needles of a high elbow and the thickness of a bee's body are fixed .

In one of these needles, God, at the beginning of the centuries, placed sixty-four discs of pure gold, the largest on the bronze base, and the others, in decreasing order of width, superimposed to the top. This is the Brahma Tower.

Day and night, the priests take turns in the occupation of transporting the tower of the first diamond needle to the third, without deviating from the fixed and immutable rules imposed by Brahma: The priest should not move more than one disk at a time and you should not place a disc other than a free needle or a larger disc. When strictly following these recommendations the sixty-four discs have been transferred from the needle in which God placed them to the third, the tower and the Brahmins will become dust and will be the end of the world.

Assuming the priests were able to make a move every second,

How long will it take to reach the end of the world?

Solution

The minimum number of moves to solve the problem is 2n - 1, being n the number of discs, in this case 64. If we carry out the calculation, we obtain that 18,446,744,073,709,551,615 movements of one second each are necessary, representing approximately 585,000,000,000 years.

You can find more information about the approach and resolution of this problem on this page and in the wikipedia.