Math ISU on Tower of Hanoi

Introduction – The Legend

In 1833, Edouard Lucas, a French Mathematician, has created a game puzzle and named it Tower of Hanoi (Bogomolny, n.d., para. 1). In truth, the inspiration of the puzzle came from an ancient legend of a Indian temple (Britannica, 2009, para. 2). In the legend, the explorers were given a tower of 64 disks, organized by having the smaller disks placed above the larger disks (Tower of Hanoi, 2010, para. 1). The explorers’ mission was to shift all the disks one by one from post one to post three and avoiding any larger disks above the smaller disks (Tower of Hanoi, 2010, para. 1). The explorers were told that once they have completed the task, the temple will demolish and the time will come for the final destruction of the Earth (Tower of Hanoi, 2010, para. 1). Now the question is: how much time will it take for the apocalypse to occur?

Get Help With Your Essay
If you need assistance with writing your essay, our professional essay writing service is here to help!
Essay Writing Service

The Tower of Hanoi is a classic puzzle game that is popular among different countries. The aim of the game is simply to make as less moves as possible and transfer all disks. The difficulty stage increases as the amount of disks increases which creates fun for people of all ages. Behind its popularity, the puzzle also brings up many mathematical ideas and concepts that are useful to predict the result of the game. This paper will be focusing on the expansion of these concepts and patterns. It will also discuss two different types of patterns presented in the puzzle and analyze how the patterns are formed. The paper will then create two formulas regarding to the patterns through the use of tables and graphs. Finally, by applying the formulas created through observing different data and values, the paper will respond to the original question of how much time will it take for the apocalypse to occur.

 

 

Observing a Strategy

To recall, in order to complete the mission, the player’s goal is to find out the least number of moves to shift 64 disks onto the third pole of the Tower of Hanoi. To comprehend better the mathematical concepts behind the puzzle, it is best to analyze simpler versions of the puzzle, such as the following 1 disk, 2 disks, and 3 disks puzzle examples.

     

From the processes shown in Figure I, II, and III, one is able to observe a strategy of making the least number of moves.

The player’s first goal should be trying to shift everything above the largest disk onto the second pole. This idea be can expressed as transferring “n-1” disks to the second pole whereas “n” represents the total amount of disks (Tower of Hanoi, 2010, para. 6). From Figure II and Figure III, it shows 3 moves expected to shift all disks except for the largest disk from the initial pole to the second pole for a 3 disks puzzle. Moreover, 3 moves are also expected to shift all disks from the first to third pole for a 2 disks puzzle. Thus, one can inform that the amount of moves that are expected to shift “n-1” disks from the initial pole to the second pole is identical to the amount of moves that are needed to shift “n-1” disks from the initial pole to the last pole. Next, after shifting “n-1” disks away from the initial pole, one will then shift the biggest disk to the final pole. This action will require one move. Lastly, the player will transfer the “n-1” disks that were previously placed on the second pole to the final pole as well. By looking at the examples, one is able to discover that the amount of moves expected for shifting “n-1” disks from the second pole to third pole also has equal amount of moves expected to transfer “n-1” disks from the initial to the last pole.

By looking at the amount of moves that are expected to resolve the puzzle for the specific number of disks, one is able to observe a recursive pattern. In fact, recursive pattern is a sequence that uses the previous term of the pattern to determine the following term (Tower of Hanoi, 2010, para. 6).

Recursive Formula

If one follows the strategy, one is making the total amount of moves required for shifting “n-1” disks from the initial pole to final pole twice (first to second, second to third), and makes one extra move for tranferring the biggest disk to the final pole.

Therefore, the relation between the amount of disks and the amount of moves expected to resolve the puzzle can be represented by the equation: 

From Table I, one is able to see the presence of the recursive sequence. The total move required from the 1 disk puzzle, 1 move, becomes the value of Mn-1 for the 2 disks puzzle. Following the same idea, the moves of the 2 disks puzzle, 3 moves, become the value of  Mn-1 for the 3 disks puzzle. Using the recursive formula, one can calculate the moves it takes to solve the following 4, 5, and n disks puzzle by applying the previous term into the formula.

However, the original question of how many moves are expected to transfer 64 disks from first to last pole still leaves unsolved. The recursive formula can be a method to find the total amount of moves required to finish the puzzle but in order to get the answer, one needs to first know the value of Mn-1, which is M63 in this case. In fact, Mn-1 is a variable that remains concealed before the previous terms are revealed. This issue brings up another obstacle to the problem and indicates a disadvantage of the recursive formula. If one wishes to solve the 64 disks puzzle, one must calculate the moves for all the number of disks that are less than 64, such as 63, 62, 61, and so on. This process can waste one a lot of time and increases the one’s possibility to mess up the answer because if one makes a mistake when calculating one of the middle terms, all the terms after that term would be wrong as well. Thus, the recursive formula is not the most logical method to solve this question.

On the other hand, even though the recursive pattern may not be most helpful in this case, but it can generate data that lead one to a non-recursive sequence in the puzzle, known as an explicit pattern (Tower of Hanoi, 2010, para. 9). An explicit pattern permits one to form an equation to find any term in the pattern without listing all the terms before it (Tower of Hanoi, 2010, para. 9). In this case, determining an explicit pattern formula would be more useful to complete the puzzle than a recursive formula.

Explicit Formula

 To begin with, one should take the values and data from Table I. These data are reorganized in the table below.

There may not seem to be an obvious explicit relationship between the number of disks and the total amount of moves. One method that individuals can use to determine the explicit pattern is to graph the data shown in Table II, setting the amount of disks as x-values and amount of moves as y-values, in order to see what if any function relationships are presented.

               

                 Figure IV

Figure IV displays a graphic understanding of the discrete data shown in Table B. Discrete data are data that can only take certain values (Discrete Data, n.d., para. 1). From the past knowledge about different types of common functions, one is able to see that the data displayed in the graph look similar to the exponential function, y = 2x . For example, the y-value is increasing as the x-value approaches positive infinity. In addition, even though the graph did not show what will happen if x approaches negative infinity, but one can still see that y is slowing approaching to its horizontal asymptote. To sum up, all of these behaviors correspond to the characteristics of the exponential function, y = 2x .

Below is a graph of the exponential function, y = 2x . As one can see in Figure V, the function shares a similar trend with the discrete data points in Figure IV

 Figure V

When comparing the two graphs, it is easier to identify the x-values of the discrete data points in Figure IV and look at their corresponding y-values in Figure V on the continuous function, then compare the two sets of y-values.

Table III compares the two sets of y-values in Figure IV and V

From Table III, one is able to see that the y-values of the exponential function,   y = 2x , are always one unit bigger than the y-values of the discrete data points, both corresponding to the same x-values.

This means that if one wishes to make the exponential function, y = 2x , lie perfectly on top of the data points, one must lower the horizontal asymptote of the function by making a vertical translation of 1 unit down.  This transformation creates the possible formula for the explicit pattern:

 

In order to verify this assumption, one can calculate the total moves by inserting the number of disks into the equation.

Table IV verifies the accuracy of explicit formula, y = 2x – 1, as it provides the same number of total moves (y-values) after applying the formula with the same number of disks (x-values).

Solving the Problem

 After successfully determining the explicit formula for the puzzle, one can now apply the formula and solve the original question of how long would it take for the apocalypse to occur, or in other words, how many moves are expected in order to transfer all 64 disks to the final pole.

 To show better understanding of the problem, the explicit formula can be modified from

“M” represents the number of moves and “n” represents the amount of disks in the puzzle.

One would simply replace n with 64 as the goal was to determine the total amount of moves required to transfer 64 disks.

To summarize, the explorers are expected to make approximately 1.84 x 1019moves in order to transfer 64 disks to the final pole and mark final destruction of the world.

Reflection

 I decided to choose this topic about the Tower of Hanoi because I used to always have the game in the corner of my room. I received the game as a gift from my grandparents when I was eleven. They told me that the game requires logic, thinking, and some math skills as well.  At first, I did not believe their description until I tried to solve the puzzle myself. I was stuck on the sixth level (6 disks puzzle) and could not figure out the solution no matter how hard I have tried. As a result, I have left the game in my room ever since. However, the failure of not solving the puzzle has made me frustrated.  I was very surprised when I saw Tower of Hanoi on the topic sheet, and I thought that it would be a great opportunity for me to understand the concepts behind the game in a deeper level since I already have mathematical knowledges about function, transformations, and discrete data. Moreover, after exploring on this topic, I will be able to continue the puzzle that I gave up solving four years ago.

While exploring the concepts behind the Tower of Hanoi, I learned to apply past knowledge that I have gained in class to solve problems. For example, I used my knowledge about exponential function and function transformations to form an explicit formula for the puzzle. In fact, I have experienced multiple obstacles in finding the explicit formula. Fortunately, I overcame the challenge through extensive research and reviewing class notes. I have also used the knowledge of a recursive pattern to connect the variables with their corresponding values. It should come as no surprise that everything in our lives are connected mathematically, no matter how small and simple it may seem. Furthemore, it is important for one to remain curious and continue to apply past knowledges in order to understand more complicated concepts. 

 

Conclusion

Referring back to the legend, in order for the final destruction of the world to occur, the explorers must make approximately 1.84 x 1019moves without making any mistakes. The solution was determined through multiple processes. First, a recursive pattern was discovered by looking at the strategy of the puzzle. Next, based on the discrete data of the first 5 terms generated from the recursive formula, an explicit formula was created through the help of graphing. Finally, by using the explicit formula, one is able find the minimum moves required to shift the given value of disks from the initial to final pole. Given these knowledges, one has the opportunity to challenge their thinking levels when solving the puzzle as to use the least amount of moves.