This mode of thinking originated when mathematician Leonhard Euler was tasked with the ‘Seven Bridges of Königsberg’ challenge in 1736. “Once you have represented the problem this way, you can spot connections to other problems you already know about.” “Many problems in discrete mathematics can be translated onto a graph, such as scenarios that involve flipping a switch or making a move in chess,” says Dan. Graphs uncover aspects of a particular scenario that might have otherwise gone unseen, in particular by connecting them to other scenarios that may be better understood. To visualise not only how many steps are needed, but exactly which steps too, the Tower of Hanoi configuration can be represented on a diagram that mathematicians call a graph. Using the formula above, we can deem that this is highly unlikely, given it would take them many billions of years to complete! Since this legend was invented by Lucas as a marketing ploy, it is hardly surprising that the underlying mathematics do not allow this apocalyptic prophecy to be put to the test. 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. 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.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |