HANOI TOWERS FUNCTION SERIES

The legend goes that young priests of a Hindu temple were tasked with moving discs of pure gold according to the rules of the puzzle – except that their Tower contained not 5 but 64 discs, and it was said that when they completed the task, the world would end. Interestingly, this formula can lead us back to the Tower of Hanoi’s supposed mythological roots. If it had four discs, it would require only 15 steps – and for three discs, only 7.

Therefore, solving the puzzle would take a minimum of 31 steps. So, if the tower had five discs, the formula would be 2⁵-1, which is 31. In this formula, S is the number of steps, and N is the number of discs. This can be written in algebraic form: S = 2 N-1 The more discs that the puzzle contains, the more steps it will take – rising exponentially, in fact. Ultimately, it involves constructing and reconstructing progressively larger ‘towers’, until the bottom disc can be moved to the third pole and the rest of the tower constructed upon it, as the text box explains in mathematical terms (See ‘Solving the Tower of Hanoi through recursion’ on the third page). The Tower of Hanoi can be solved using recursion too, which helps mathematicians find the way to solve the puzzle in the fewest number of steps possible.

You then repeat this process, dividing the pile into two twenties, two tens, and so on, until you narrow it down to the one coin. You can select the lighter pile and discard the other forty coins all at once. A faster way would be to divide the pile into two piles of forty and weigh these two piles against one another.

To find this lighter coin, one solution would be to weigh and compare two coins at a time to see if there is any difference in weight – but this method would take ages. All the coins weigh the same, apart from one that weighs slightly less. For instance, imagine you have eighty coins and a set of balance scales. “Recursion is the extremely useful idea of solving a large problem by reducing it to smaller instances of the same problem,” says Dan. Professor Dan Romik, of the University of California, Davis, has investigated the Tower of Hanoi and, despite the puzzle’s apparent simplicity, has shown that it continues to yield new surprises. However, underlying the puzzle are some key mathematical ideas – even if we might not appreciate them when solving it. This puzzle quickly reached fame as the brainteaser now known as the Tower of Hanoi.ĭespite it seeming initially perplexing, in truth the Tower of Hanoi is a problem that even amateur puzzlers can solve with a bit of lateral thinking. However, the catch is, a larger disc can never sit on top of a smaller disc. The aim is to move the tower, one disc at a time, over to the right-hand pole.

HANOI TOWERS FUNCTION SERIES

There are three poles in a row, the one on the left containing a series of discs of decreasing size, with the other two, empty. In 1883, a French mathematician named Édouard Lucas came up with an intriguing scenario.

Hanoi towers function