Aquila Children's Magazine AQUILA Magazine Best Bits | Page 41

More layers? Now we’ve dealt with three layers, do you think you can figure out the minimum number of moves for four layers? Would it take many more steps, or just a few? Even better, we can also solve five layers in the same way. Moving five layers means moving the smallest four layers to Area B, then moving the largest one to Area C, and finally stacking the smallest four on top. The solution for five layers is: The trick to solving the game for four layers is that the solution relies on knowing the quickest way to solve for three layers. four layer solution + 1 move + four layer solution OR 15 + 1 + 15 = 31 moves! In order to get Layer 4 (the largest layer) free to move into Area C, all the other layers must be sitting (in order!) in Area B. That means, you’ll need to: – move Layers 1, 2, and 3 to Area B in seven moves, using the solution for three layers (but swapping Area B and Area C at each step) – move Layer 4 to Area C, and then: – move Layers 1, 2, and 3 from Area B to Area C, using the solution for moving three layers again. Yep. That is exactly what you’re seeing. The (Caaaake!) Tower of Hanoi is an example of a recursive puzzle. Once you know how to solve the puzzle for a certain number of layers, you can also solve it when the next layer is added, and the next one and the next one and… you get the idea! Even without physically doing the 4-layer tower, we can work out the number of moves as follows: three layer solution + 1 move + three layer solution OR 7 + 1 + 7 = 15 moves! Now that ’s pretty cool! Ooh, I am starting to see a pattern here! With a bit of maths shuffling and shifting that I won’t get into, we can also work out a closed form equation (i.e. not recursive!) for the number of moves required: x n = number of moves it takes for n layers x n = 2 n – 1 The minimum number of moves to solve this puzzle gets really big, really fast! The shortest solution for 10 layers is over a 1,000 moves, and 20 layers takes more than one million moves! Can we just stick to four layers for now, eh Calculata? Ed Tip: 2 n (say it as ‘two to the power of n’) just means 2 multiplied by 2 n times. Like 2 3 = 2x2x2, and 2 4 = 2x2x2x2, and 2 5 = 2x2x2x2x2 and so on. You can calculate the minimum number of moves required for a certain number of layers like this: x n = number of moves it takes for n layers x n–1 = number of moves it takes for n–1 layers x n = x n–1 + 1 + x n–1 = 2x n–1 + 1 This is called a recursive equation, because you need to know the number of moves for n-1 layers in order to calculate the number of moves for n layers. Here ‘n’ stands for ‘number of layers’. So if you want to work out how many moves for 7 layers, then n=7. WHY IS THE PUZZLE CALLED THE (CAAAAAAKE!) TOWER OF HANOI? If one disc is moved per second, how long will this take the priests to complete? larger one, from the left needle to the right needle. Upon completion of the puzzle, the legend claims the world will end. If the priests work at a speed of one move per second it will take 5.85x10 11  years (that’s 58.5 billion years!). The current age of the Universe is reputed to be, according to various sources, around 13.77 billion years. Therefore, it could take the monks over four times the current age of the Universe to complete their task. I hope none of them need a pee. The puzzle was invented by French mathematician named Édouard Lucas. It’s based on a legend he had heard (or possibly made up) about an Indian temple (nowhere near Hanoi, that’s in Vietnam) where a mathematical puzzle, also known as The Tower of Brahma was used to discipline young priests. The legend says that, since the beginning of time, 64 gold discs ranging in size have surrounded three diamond needles in a large room inside the temple. The priests have been working for centuries to move the discs, each one on top of a