The Tower of Hanoi (also known as The Tower of Brahma and The
End of The World Puzzle) was invented in 1883 by Edouard Lucas, a
A Good
introduction
French mathematician. It is said that he designed the puzzle based on a legend of a Hindu Temple. In the beginning of time the priests in the temple were given a tower of 64 gold disks, each smaller in size then the disk beneath. They were to transfer the disks from one of three poles to another without allowing any disk to be placed on top of a smaller one
(as the weight from the disk will crush the one beneath it). It is said that when the day the priests successfully transfer the 64 disks from one pole to another, the world will crumble and vanish. If this legend was true, could there be a way of predicting the end of the world?
The Tower of Hanoi is a classic puzzle for all ages as the number of disks creates endless levels of difficulty and fun. Though the aim of this game is simple, it reveals many mathematical concepts and patterns through the process of playing the puzzle. These patterns will be explored and analyzed and the legend of The Tower of Hanoi will be put to the test.
A Aim identified Finding a Pattern
The task is to find out how many moves it takes 64 disks to transfer from one pole to another pole of the Tower of Hanoi. Solving the puzzle using a smaller number of disks will be easier to analyze and understand. Let’s look at how the Tower of Hanoi is solved using 1, 2, and 3 discs.
Figure A. One Move
Moves 1: move disk 1 to post c
Mathematics SL and HL teacher support material
1
Example 9: Annotated student work
Figure B. Three Moves
Move 1: move disk 2 to post B
Move 2: move disk 1 to post C
Move 3: move disk 2 to post C
B These diagrams are helpful, but better clarity could be achieved by identifying which is disk 1 and 2.
Figure C. Seven Moves
Move 1: move disk 3 to post C
Move 2: move disk 2 to post B
Move 3: move disk 3 to post B
Move 4: move disk 1 to post C
Move 5: move disk 3 to post A
Move 6: move disk 2 to post C
Move 7: move disk 3 to post C
The number of moves it takes to complete the puzzle for an amount of discs is a recursive pattern. A recursive pattern requires information from the previous term of the pattern to determine the following term. In this situation, it is the number of moves required for n discs to transfer from A to C.
Figure 1-3 shows that one must first transfer n-1 discs (n being
A Unsure
what this refers to
the number of discs in the puzzle) to pole B. In Figure C it takes three
Mathematics SL and HL teacher support material
2
Example 9: Annotated student work
moves to transfer two discs to pole B (step 3 of Figure C). The number of moves required shall be the variable M.
The next step is to transfer the remaining disc from A to C (step 4 of Figure C).
The last step is to transfer the discs from pole B to C. It will require the same number of moves required in the first step also known as the variable M. In Figure C it takes three moves to transfer n-1 discs from pole B to pole C (step 7 of Figure C).
Reflecting on the steps you can see that to solve the puzzle you move M amount of moves twice (from A to B, and from B to C). You also make a single move from A to C. Mathematically the recursive pattern should look like this:
# of discs
Total Moves
Equation 2M + 1
1
1
2(0) + 1 = 1
2
3
2(1) + 1 = 3
3
7
2(3) + 1 = 7
B Not an
equation
Table A.
In Table A under the Equation column, you are able to clearly see why there is a recursive pattern present. The total moves from the 1 disc puzzle become the M of the second puzzle as shown in the bold and black numbers. The total moves for the 2 disc puzzle become the M of the third puzzle as shown in the bold and grey numbers. Using the recursive pattern, you are able to find the number of moves it takes for a
4, 5 disc puzzle and for an n disc puzzle as shown in Table B on page 4.
