Patterns, Intuition and Enlightenment: The Towers of Hanoi

Let’s start where the last post ended:

“A major pursuit of mathematics is to seek and analyse patterns, and as we’ll see, the identification of patterns reduces uncertainty. This incites pleasure and unlocks the doorway to positive aesthetics responses…”

So, I thought before moving on that I’d pick one of an infinite number of possible examples to seek and analyse pattern, thus reducing uncertainty. It wasn’t easy picking a piece of mathematics to do this – I wish I could go deep into 50 patterns – but I promise that I will do my best with this example.

Let’s take a lovely little puzzle called the Towers of Hanoi puzzle (or Towers of Brahma), in which the aim is to move all of the disks on the first pillar to the third pillar in the least number of moves. Only one disk can be moved at a time and it is not permitted to put a larger disk on top of a smaller disk.

In the video above, we’re left with 10 disks on the first pillar – how many moves do you think it will take to move all of the disks to the third pillar?

It might be that your intuition is pulling a curtain over the depth of the problem (as intuition often does) – i.e. you think it’s a fairly simple game and the number of moves can’t be much more than one hundred, for example. Alternatively if you’re more attuned to mathematical thinking you may have already began to gain a sense of some complexity in the puzzle. Whatever the case there’s little point moving forward without doing what mathematicians do best, i.e. seek and analyse patterns. So let’s develop an understanding by building up from simpler cases. As you saw, the three disk puzzle takes 7 moves, and the four disk puzzle requires 15 moves. See the table below to find out how much you were fooled by your basic intuition.

Number of Disks, d

Number of Moves, M

1

1
2

3

3

7

4

15

5

31

6

63

7

127

Looking at the pattern in the right column of the table, you may have noticed that we can take the previous number of moves, multiply it by two and add one, and we’ll get the answer for the next row. Hence, there are 255 moves for the eight disk puzzle, 511 moves for the nine disk puzzle and 1023 moves for the ten disk puzzle. That might be something of a surprise, especially if you haven’t had a go at the game or analysed it in any detail. But it is lovely that we’ve used patterns to understand something about the minimum number of moves required.

If you were intrigued to know the minimum number of moves for a fifty disk puzzle it’d be cumbersome to have to multiply by two and add one continuously to get the answer. This is why we look for a relationship between the number of disks and the number of moves. The pattern almost doubles each time which makes it exponential (or geometric), and it is simple by inspection in this case to see the relationship between the number of disks, d, and the number of moves required, M.

M = 2d – 1

The simplicity of this formula from a game that seems partially complex will hopefully leave you with a sense of satisfaction that uncertainty has been reduced and at least a slight feeling of aesthetic pleasure!

Start of Interlude: The Dangers of Intuition in Mathematics

Time-out! True mathematicians would be dismayed to let this stand on such shaky premises. As Marcus du Sautoy remarks in his popular book, “The Music of the Primes,”

“The mathematician is obsessed with proof and will not be satisfied simply with experimental evidence for a mathematical guess…[indeed] Goldbach’s conjecture has been checked for all numbers up to 400, 000, 000, 000, 000 but has not been acknowledged as a theorem. Most other scientific disciplines would be happy to accept this overwhelming numerical data as a convincing argument, and move on to other things.” (p. 31)

The point here is that mathematicians do not trust their intuition. We have no idea whether that pattern will continue forever, or break down at some unknown point – right now we’re relying on a very small sample of data alongside an intuition that pattern will continue. The funny thing about intuition is that it reminds me of that friend we all have who somehow manages to convince us to do something we’re not 100% sure about. At times, it leads us to great experiences in which we wondered why we were ever worried in the first place, but every so often we’ll find ourselves in a situation we wished we’d never been a part of. Intuition is absolutely that same friend to a mathematician – sometimes it leads us to fruitful pathways, but if left unchecked, it can cause us huge problems down the road.

Probably the most famous example of intuition leading a mathematician astray presented itself in number theory, in which Ramanujan thought that his function approximating the number of primes below a given number would always predict less than the actual number of primes. John Littlewood proved that there existed a number in which Ramanujan’s function would begin to predict more than the actual number of primes (actually, that it would alternate between less and more forever). Then, some years later in 1933, Stanley Skewes found such a number which is so big you can’t compare it to anything in the observable universe, it’s 10101034. Given that estimates of the number of atoms in the observable universe lie around 1070, which is minuscule in comparison with Skewes’ number, a non-mathematician might forgive Ramanujan for relying on his intuition. If you’d like to know more about this I’d advise watching the wonderful Numberphile video which explains it with simplicity and clarity (Grime, 2015).

I can’t now move on without peering into a few more examples…they’re just too interesting not to point out.

  • Moser’s circle problem (14-16 years example) – this involves splitting a circle into discrete regions by creating points on the circumference and joining them with chords (with no three chords being allowed to pass through the same point).  If you do so, you get the following progression:

Picture1.png

The first 5 iterations follow a simple exponential pattern for the number of regions, very similar to that of the Towers of Hanoi puzzle: 1, 2, 4, 8, 16.

The sixth iteration is more intriguing; instead of giving 32 regions as intuition would suggest, it gives 31 regions. Defining as the number of vertices, and R as the number of regions, we obtain a formula which is much more complex than our intuition might have suggested:

R = 124(n4 – 6n3 + 23n2 – 18n + 24)

On the surface this formula looks down right atrocious –  how dare you be so complicated given the simplicity of the patterns in the first 5 iterations! It certainly doesn’t enlighten my understanding – which if you go back to the previous post – is a major element of mathematical aesthetics and one of the goals of mathematics. If you’d like a deeper understanding of this formula – and you have some background knowledge of Pascal’s triangle – check out this lovely video by 3Blue1Brown.

  • The Powers of 11 and Pascal’s Triangle (16-18 years Example) – Have you ever noticed the connection between the rows of Pascal’s Triangle, and the powers of 11? It behaves beautifully, up until the 6th row…

Screen Shot 2019-02-19 at 10.41.35

This is horrible at first site, but then once you look at the binomial expansion of (1 + 10)1, (1 + 10)2, (1 + 10)3, …, (1 + 10)5, then you quickly become enlightened as to the reasoning behind the breakdown.

  • The Borwein Integral (post-18 years example) – this churns out π2 in the first seven iterations, but then ‘mysteriously’ churns out a number ever-so-slightly less on the eight iteration.

Picture1

Image: Wikipedia (https://en.wikipedia.org/wiki/Borwein_integral)

End of Interlude: The Dangers of Intuition in Mathematics

I hope you found that to be an interesting tangential path on our walk through the landscape of mathematics, but let’s make our way back to the previous path. Intuition is essential, but never sufficient, and that is why proof is more important to a mathematician than butter is to bread. I’ll continue to come back to the notion of proof, understanding and aesthetics later in later posts. As I said in the previous post, the truth of the matter is sometimes only the first stage in the game of mathematics. If the proof doesn’t enlighten the mathematician on the meaning of why something is true, then we love to get inside the engine of the car to see how everything works. That is if we have the tools to do so of course…

To give some insight on enlightenment with the Towers of Hanoi, see the pictures below with a five disk puzzle. A very important part of this puzzle is to free up the bottom largest disk so as to be able to move to the 3rd pillar. In order to free this up, we need move all of the disks above it to the 2nd pillar. In this case that means we need to make 15 moves to move all 4 disks to the 2nd pillar.

Picture1

Fig 1: www.softschools.com, Fun Games, Logic Games

Once this has been achieved, we need one move to transfer the largest bottom disk to the 3rd pillar. After that, we then have to move all four disks which are currently residing on the 2nd pillar to the 3rd pillar and this requires another 15 moves. Hence, in this case, we have 15 moves + 1 move + 15 moves = 31 moves for the five disk puzzle.

Picture2

Fig 2: www.softschools.com, Fun Games, Logic Games

If you think about it, this reasoning applies to any number of disks. We always follow the same steps:

  1. Move all of the disks except the bottom one to the second pillar.
  2. Move the bottom disk to the third pillar.
  3. Move all of the disks from the second pillar to the third pillar.

Using some symbolism, if we say that the number of moves for the four disk puzzle is denoted by M4 and the number of moves needed for the five disk puzzle is M5, then:

M5 = M4 + 1 + M4

M5 = 2M4 + 1 

This agrees with our initial observation of the pattern in the table, i.e. multiply by two and add one. With any number of disks, n, we have a recurrence relation which tells us that if we know the previous number of moves, then we can find the number of moves for when we add another disk.

Mn+1 = 2Mn + 1

At this point, we have reasoning which gives us confidence that this pattern continues in the same way forever, no matter how many disks we have on the first pillar – no more intuition required. We can then use basic recurrence relation mathematics to generate the formula given previously, M = 2d – 1, but this case was simple enough to see the relationship via inspection.

Going back to the previous post, we now see why mathematicians would neglect to discuss the symbolism and equations of mathematics; because they are merely the tools we use to reduce uncertainty, analyse pattern, develop relationships, and crucially, to understand these relationships. Every part of the process can be aesthetically pleasing for a mathematician, as you’ll continue to find out!

References:

  1. du Sautoy, Marcus (2003). The Music of the Primes: Searching to Solve the Greatest Mystery in MathematicsHarperCollinsISBN 0-066-21070-4.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s