Convoluted metaphor aside, no one had been able to solve this problem until Hinz used Hanoi graphs to figure out the average distance is 466/885 (given the length of one side of the triangle is 1). However, in many cases stepping back from the problem, looking at its connections to other areas of mathematics provides an easier route to your answer – you could just climb over the boulder. At first you might try to push the boulder or dig through it – facing the problem head on.
Whilst being quite beautiful and interesting, one still might ask: what is the purpose of these connections? How are they useful? Firstly, let’s entertain this question: suppose you travel around Sierpinski’s triangle without ever leaving the fractal, what is the average distance between two points? Well, a lot of times in mathematics problems are like boulders, blocking the middle of the road. Step 3 is to repeat step 2 in the smaller triangles infinitely many times. Step 2 is to divide the equilateral triangle into 4 smaller congruent equilateral triangles, discarding the central triangle. Step 1 is to draw an equilateral triangle. It can be generated from another infinite process. This is a fractal, known as Sierpinski’s triangle. For example, disk one and disk 3 on peg 2, with disk 2 on peg 3 will look like (2, 3, 2). The positions are encoded using a triple. When graphing all the possible configurations of a game of 3 disks and 3 pegs you get a sort of ‘triangle network’, which is officially called a Hanoi graph. What’s particularly fascinating to me about this puzzle is its connection to Sierpinski’s triangle. This part is pretty simple, as it just involves substituting the new equation into one we already know is true for all values of n. Lastly, the statement needs to be checked to ensure that it is true for all values of n, as knowing it is true for the first 6 values, while a good indication, doesn’t prove it is true for n ≥ n 0. There seems to be a pattern: T n = 2 n – 1 for n ≥ 0 Looking at the first few values for T n could help: However, for large values of n it would take a long time to work out – so a nice, neat closed form equation for T n would be more useful. This recurrence equation can compute for any value of n. Hence, transferring n disks requires 2T n-1 + 1 moves: Move T n-1 disks to another peg, transfer the largest disk, then transfer T n-1 disks back onto the large one. This process can be quite easily generalized. First get the smallest two disks off the largest disk (requiring T 2 moves), then transfer the largest disk to the other peg (requiring one move) and lastly transfer the two smaller disks back onto the larger one (requiring another T 2 moves).
iostream01-wikipedia.jpg "hanoi towers morbido")
HANOI TOWERS MORBIDO HOW TO
Looking more closely at how to solve for three disks, gives some clues on how to solve on a larger scale. Thus, for the small values of n we can state: T 0=0, T 1=1 and T 2=3. The first step to solving this problem is to establish appropriate notation: T n will be the minimum number of moves required to transfer n disks, following Lucas’s rules.
This is part of the reason I find this problem so interesting it is a great example of generalizing to spot patterns and recurrences consequently, it serves as a useful introduction to the mathematics of computer science and algorithms. Instead of focusing on how many moves it will specifically take for the Tower of Hanoi’s 8 disks or the tower of Brahma’s 64 disks – generalization helps, as it allows you to scale down the problem. One might be confused at first, it’s not immediately obvious that the puzzle has a solution, just move the tower from one peg to another in accordance to the rules, what’s the challenge? Well after a small go at the puzzle or with a little thought, the question arises: what is the best way to do this? What’s the smallest number of moves required to solve the puzzle for n disks?
Luckily for people trying to solve the puzzle, the tower of Hanoi is a little smaller than the Tower of Brahma, involving only 8 disks instead of 64. This grand story in fact accompanies a toy puzzle, the Tower of Hanoi, invented by Edouard Lucas, a French mathematician in 1883.
0 kommentar(er)
