The Tower of Hanoi is one of the more popular puzzles amongst recreational mathematicians and in education. Almost everyone is familiar with it and the story that usually accompanies it - often couched in terms something like this...
“There is a legend of a temple near Hanoi in Vietnam. The temple has three golden poles. One one pole sits 64 golden discs of different sizes. The rings are arranged with the largest at the base progressing in order to the smallest disc which sits on top of the pole. The monks who tend the temple have been charged with moving the rings from their current pole to the end pole - one disc at a time - but there is a special rule that they must follow. They must never place a larger disc on top of a smaller one. When they complete this task the world will end. How many moves will it take the monks to do this?”
We probably don’t need to work ourselves up into a sweat worrying about the monks finishing their task which will signify the end of the world. It has been calculated that if the monks were able to move the one disk per second it would take them around 585 billion years to complete the task - 18,446,744,073,551,615 turns. In classrooms the number of disks is usually drastically reduced to around five in the early stages - which is enough to prompt some interesting explorations. In this age of the Internet there are several interactive versions - which have the advantage of being readily customised and also of making suggestions for optimal moves. Examples can be accessed here and here.
It is a great puzzle - a surefire hit in the classroom. But what makes me love this puzzle so much is the simple fact that it is a hoax. Traditionally there was no such legend in Vietnam - or in India either, which is another popular location for the site of the temple. The whole thing is the invention of mathematician Edouard Lucas. When the puzzle was first published in 1883 it appeared complete with legend and was credited to N. Claus de Siam (an anagram of Lucas d’Amiens - Amiens being the town of his birth).
Lucas was a significant mathematician in his own right - so significant that he has his own number series named after him - the Lucas sequence (similar to the Fibonacci sequence but instead of starting 1,1,2,3,5,7... Lucas’ starts at with 2,1,3,4,7,11,18...) and he developed a test for large prime numbers still in use today.
Lucas’ death is also worthy of interest - he is possibly the only mathematician in history to die as a result of a piece of crockery. A clumsy waiter dropped a plate which broke and shard from the plate cut Lucas on the cheek. The cut became infected and he later died of erysipelas - a serious streptococcus infection.
The myth and the puzzle are well known … but the puzzle has a rather curious property that is less so. The movements of the pieces can be represented in a graph as depicted here.
This bears an uncanny resemblance to to the famous Sierpinski triangle- which is a fractal. The fact that the movements of a game can be linked to fractals is, to say the least, intriguing. (More on this at the source.)
The Tower of Hanoi has recently become a movie star. A disguised version of it appears in the move “Rise of the Planet of the Apes” - disguised, fittingly given the manner in which it as first published, as the Lucas Tower which was used to test the intelligence of the apes.
What can we learn from this wondrous hoax? When it comes to education sometimes a touch of showmanship and playfulness can improve a strictly mathematical experience. It is important that the mathematics remains central - but the “power of story” is a significant tool to generate engagement and interest - which may contribute to the “holy grail” of teaching; a self-directed learner. We can help foster this when we show our students that there is more to mathematics than just the numbers.
Undirected graph of movements: http://en.wikipedia.org/wiki/File:Tower_of_Hanoi-3.svg
Sierpinski triangle: http://upload.wikimedia.org/wikipedia/en/thumb/8/88/Sierpinski_Triangle.svg/220px-Sierpinski_Triangle.svg.png
“There is a legend of a temple near Hanoi in Vietnam. The temple has three golden poles. One one pole sits 64 golden discs of different sizes. The rings are arranged with the largest at the base progressing in order to the smallest disc which sits on top of the pole. The monks who tend the temple have been charged with moving the rings from their current pole to the end pole - one disc at a time - but there is a special rule that they must follow. They must never place a larger disc on top of a smaller one. When they complete this task the world will end. How many moves will it take the monks to do this?”
We probably don’t need to work ourselves up into a sweat worrying about the monks finishing their task which will signify the end of the world. It has been calculated that if the monks were able to move the one disk per second it would take them around 585 billion years to complete the task - 18,446,744,073,551,615 turns. In classrooms the number of disks is usually drastically reduced to around five in the early stages - which is enough to prompt some interesting explorations. In this age of the Internet there are several interactive versions - which have the advantage of being readily customised and also of making suggestions for optimal moves. Examples can be accessed here and here.
It is a great puzzle - a surefire hit in the classroom. But what makes me love this puzzle so much is the simple fact that it is a hoax. Traditionally there was no such legend in Vietnam - or in India either, which is another popular location for the site of the temple. The whole thing is the invention of mathematician Edouard Lucas. When the puzzle was first published in 1883 it appeared complete with legend and was credited to N. Claus de Siam (an anagram of Lucas d’Amiens - Amiens being the town of his birth).
Lucas was a significant mathematician in his own right - so significant that he has his own number series named after him - the Lucas sequence (similar to the Fibonacci sequence but instead of starting 1,1,2,3,5,7... Lucas’ starts at with 2,1,3,4,7,11,18...) and he developed a test for large prime numbers still in use today.
Lucas’ death is also worthy of interest - he is possibly the only mathematician in history to die as a result of a piece of crockery. A clumsy waiter dropped a plate which broke and shard from the plate cut Lucas on the cheek. The cut became infected and he later died of erysipelas - a serious streptococcus infection.
The myth and the puzzle are well known … but the puzzle has a rather curious property that is less so. The movements of the pieces can be represented in a graph as depicted here.
This bears an uncanny resemblance to to the famous Sierpinski triangle- which is a fractal. The fact that the movements of a game can be linked to fractals is, to say the least, intriguing. (More on this at the source.)
The Tower of Hanoi has recently become a movie star. A disguised version of it appears in the move “Rise of the Planet of the Apes” - disguised, fittingly given the manner in which it as first published, as the Lucas Tower which was used to test the intelligence of the apes.
What can we learn from this wondrous hoax? When it comes to education sometimes a touch of showmanship and playfulness can improve a strictly mathematical experience. It is important that the mathematics remains central - but the “power of story” is a significant tool to generate engagement and interest - which may contribute to the “holy grail” of teaching; a self-directed learner. We can help foster this when we show our students that there is more to mathematics than just the numbers.
~~~~~~~~~~~~~~~~~~~~~~~~
Undirected graph of movements: http://en.wikipedia.org/wiki/File:Tower_of_Hanoi-3.svg
Sierpinski triangle: http://upload.wikimedia.org/wikipedia/en/thumb/8/88/Sierpinski_Triangle.svg/220px-Sierpinski_Triangle.svg.png
If you enjoyed this post you may enjoy my other maths related posts available via the maths page or by clicking here.
Nice blog - Thanks, I love it when someone points out something new about something you have been playing with for a long time. The pattern of movements is great!
ReplyDeleteThanks James, glad you like the blog post. Like you, I love it when some-one makes a connection between mathematical concepts or adds another layer to the onion of appreciation. When I saw the “movement map” for the solution of this related to the Sierpinski triangle it really made me stop and wonder why on earth that might be. I think it is moments like that is really when maths is at its most powerful – if we reacted like this then we can hope for the same response from students.
ReplyDeleteAgain, thanks for your comment and for taking the time to make contact.
Cheers
Neville