Tower of Hanoi

The Tower of Hanoi is a classic game of patience. In its simplest form, the tower comprises a rod holding three disks and two empty rods. The aim is to rebuild the tower on a new rod. Only one disk may be moved at a time and no disk may be placed on top of a smaller one. The third rod serves as an interim point.

History

The game was invented in 1883 by the French mathematician Edouard Lucas (d'Amiens) from Saint Louis secondary school. He initially published it under the pseudonym Professor N. Claus de Siam from Li-Sou-Stian secondary school. In a pseudohistorical guise, Lucas contrived a tale about Indian monks in a large temple in Benares who have to move the Tower of Brahma, which consists of sixty-four golden disks. When they finish, the temple will be destroyed and the world will end. Theoretically, 2^64 – 1 moves are required to complete the task, a twenty-digit number. If one disk is moved per second, the entire process will take hundreds of billions of years.

Mathematics

In its simplicity, the tower of Hanoi is an excellent example of a problem that can be solved recursively. If the solution for n disks is known, then a solution for n + 1 disks can be obtained and thus the problem can be solved for any number of disks. For n disks, at least 2^n – 1 steps are needed.

The numbers of the form 2^n – 1 are called Mersenne numbers. They are of particular interest because among them, with the help of a computer, the largest known prime numbers have been found. The question of whether there are an infinite number of Mersenne primes is still unanswered.