Classic Problem - Tower of Hanoi

The Tower of Hanoi is an ancient mathematical challenge.
Exploring and noticing Working systematically Conjecturing and generalising Visualising and representing Reasoning, convincing and proving
Being curious Being resourceful Being resilient Being collaborative

Problem



In this problem, you will be working on a famous mathematical puzzle called The Tower of Hanoi. There are three pegs, and on the first peg is a stack of discs of different sizes, arranged in order of descending size. The object of the game is to move all of the discs to another peg. However, only one disc can be moved at a time, and a disc cannot be placed on top of a smaller disc.

The video below shows the most efficient way of moving the discs from one end to the other, starting with 3, 4, 5 or 6 discs.



Watch the video. You might like to pause it at various points. Can you predict what will happen next? What patterns can you see?

Click below to see videos for 7, 8, 9 and 10 discs. Do the patterns that you noticed continue?







Explain how you could work out the number of moves needed for the Tower of Hanoi puzzle with $n$ discs.

There is a legend that a 64-disc version of the Tower of Hanoi is being played out in a temple, and when the final move is made, the world will come to an end. If one move is made each second, how long would it take to complete the game with 64 discs? Do we need to worry yet, if the first disc was moved at the very beginning of time?