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