Calculating the minimum number of moves to complete the puzzle
The smallest number of moves needed to move the discs from peg one to peg three is three moves.
No moves:
As we have just seen it takes three moves to move the top two discs off the third disc...
After three moves:
...then one more move to move the third disc...
After four moves:
...then three more moves to move the top two discs back onto the third disc.
After another three moves:
We have taken 3+1+3=“7” moves to complete the puzzle for three discs. We can now see a pattern.
The minimum number of moves needed to do the puzzle for four discs will be 2 times the number of moves for 3 discs plus 1. 7+1+7=2x7+1=15. Now work out the number of moves for 5 discs using this pattern.
| number of discs | calculate number of moves | minimum number of moves |
|---|---|---|
| 2 | 3 | 3 |
| 3 | 3+1+3 | 7 |
| 4 | 7+1+7 | 15 |
| 5 | 15+1+15 | 31 |
Here is a quicker way to calculate the number of moves required to complete the puzzle. Notice that every time we add a disc we take the previous number of moves, multiply that by 2 and add 1. For 4 discs the minimum number of moves is, 2x7+1=15. From this we can make a mathematical rule. To work out the number of moves required for 4 discs take four 2's, multiply them together and subtract 1.
2x2x2x2-1=16-1=15.
| number of discs | calculate number of moves | minimum number of moves |
|---|---|---|
| 2 | 2x2-1 | 3 |
| 3 | 2x2x2-1 | 7 |
| 4 | 2x2x2x2-1 | 15 |
| 5 | 2x2x2x2x2-1 | 31 |
This puzzle was first published by Edouard Lucas, a French mathematician. Under the name M Claus, he published, in 1883, the puzzle in his four volume book on recreational mathematics, Récréations mathématiques. Notice that Claus has the same letters as Lucas, so Claus is an anagram of Lucas.
It is thought that his use of the name “The Tower of Hanoi” was influenced by the French colonial interest in south east Asia.
In 1884 another French mathematician, De Parville, made up this story commonly associated with the puzzle.
“In the great temple at Benares, says he, beneath the dome which marks the centre of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Bramahns alike will crumble into dust, and with a thunderclap the world will vanish.”
W W R Ball, Mathematical Recreations and Essays, page 304
Acknowledgement: Created by Dave Collins, Shell Questacon Science Circus.