Rationale-

The main reason for choosing the Tower of Hanoi as my internal assessment was because I was interested in the concept of series and sequences. Also this puzzle showed some real life applications of mathematics which was also one of the reasons I choose this. Also the least time for the legend of Hanoi was already found so I was fascinated with idea of finding the longest amount of time for the legend of Hanoi using non-repetitive steps. For this internal assessment the equipment shown in the pictures were used in order to find any kind of patterns formed practically and also to check if the formula formed was accurate.

Introduction- The Tower of Hanoi is a renowned problem in recreational mathematics which is also known as the Tower of Bramha or Lucas Tower which is a mathematical puzzle and was first devised by the French mathematician Edouard Lucas in 1883. This basically consists of three poles along with some disks usually three which is originally stacked in one pole. These disks are put in ascending order with smallest disk being on the top. The main goal of this puzzle is transfer all the disks from the first pole to the rightmost one shifting one disk at a time without placing a larger disk on a smaller one in minimum amount of moves. As per a legend there is temple containing three poles with 64 golden disks and when moving the disks from the leftmost pole to the rightmost will be done, that would mean the end of the world. This mathematical puzzle helps in understanding the theories of sequences, series and patterns just by going through the course of the game.

Although the least time taken to move these 64 disks is already found. In a modification to this we will determine the largest amount of time taken by taking as many moves as possible without repeating any previous configuration of the rings for these 64 disks. Method- In order to obtain a formula for this puzzle we first need to discover a pattern which would be done by testing the puzzle using a total of 3 disks. The maximum moves without repetition of previous configuration of the rings with respective disks are shown in the diagrams below:

Disk Colour Pole Name

Disk 1 Leftmost Pole X Disk 2 Middle Pole Y Disk 3 Rightmost Pole Z

Diagram 1:

Total 2 Moves with one disk-

1. Move Disk 1 to Pole 2 2. Move Disk 1 to Pole 3

Diagram 2:

Total 8 moves with two disks-

1. Move disk 1 to Y 2. Move disk 1 to Z

3. Move disk 2 to Y 4. Move disk 1 to Y

5. Move disk 1 to X 6. Move disk 2 to Z

7. Move disk 1 to Y 8. Move Disk 1 to Z

Diagram 3:

Total 26 moves with three disks (shown without pictures):

1. Move from X to Y 15. Move from Y to X

2. Move from Y to Z 16. Move from Z to Y 3. Move from X to Y 17. Move from Y to X 4. Move from Z to Y 18. Move from Y to Z 5. Move from Y to X 19. Move from X to Y 6. Move from Y to Z 20. Move from Y to Z 7. Move from X to Y 21. Move from X to Y 8. Move from Y to Z 22. Move from Z to Y 9. Move from X to Y 23. Move from Y to X 10. Move from Z to Y 24. Move from Y to Z 11. Move from Y to X 25. Move from X to Y 12. Move from Z to Y 26. Move from Y to Z 13. Move from X to Y 14. Move from Y to Z

In this puzzle we see a recurrence relation forming as we can use previous

term(which is the number of moves) in order to find the next term.

Number of disks Number of Moves

Difference between number of 1 2 moves: 6 2 8 18 3 26 4 80 54

Ratio: 18 ÷ 6 = 3

54 ÷ 18 = 3

By seeing the differences in the number of moves we see a ratio forming

which is 3. And as this is a recurrence relation we can form one part of the formula using information above which is:

TN = 3TN-1

Number of Disk(N) 3TN-1 = TN

1 3(0)= 0 2 3(2)= 6 3 3(8)= 24 In this we can see that there is a difference of between the actual moves taken in the puzzle and what we find from TN = 3TN-1 :

 2-0 = 2  8-6 = 2  26-24 = 2

So from this we can find a recurrence relation. We can therefore add 2 to the formula which would give us the actual number of maximum non repetitive steps which is:

TN = 3TN-1 + 2

Number of Disks Number of Moves using

Fomula(T = 3T + 2) N N-1

1 2 2 8 3 26 4 80 5 242 6 728 7 2186 Derivation of Equation using y = 𝑎𝑏 𝑥 + 𝑐 :  When x = 1 then y = 2  When x = 2 then y = 8  When x = 3 then y = 26

Therefore using the above values we can form the equations:

= 2 = 𝑎𝑏 + 𝑐 1

= 8 = 𝑎𝑏2 + 𝑐 2

= 26 = 𝑎𝑏3 + 𝑐 3 By equating the equations 1 and 2 we get the following:

= 𝑎𝑏2 − 𝑎𝑏 = 6 = 𝑎𝑏(𝑏 − 1) = 6 4 By equating the equations 2 and 3 we get the following:

= 𝑎𝑏3 − 𝑎𝑏² = 6 = 𝑎𝑏²(𝑏 − 1) = 18 5 Now by equating the equations 4 and 5 we get the following:

𝑎𝑏²(𝑏−1) = 18 = 𝑎𝑏(𝑏−1) = 6 ∴𝑏 = 3 Now we put the value of b in the equation 4:

= 𝑎𝑏(𝑏 − 1) = 6 = 𝑎(3)(2) = 6

∴ 𝑎= 1 Now we put the value of a and b in the equation 1:

= 2 = 𝑎𝑏 + 𝑐 = 2 = (1)(3) + 𝑐 =2-3= 𝑐

∴ c = −1 To find the formula for the maximum number of non-repetitive steps using any particular number of disks we need to put the values of a,b and c in y = 𝑎𝑏 𝑥 + 𝑐 which would give us the formula :

= y = 𝑎𝑏 𝑥 + 𝑐

= y = (1)(3)𝑥 + (−1)

= y = 3𝑥 − 1

∴ TN = 3 n – 1 Graph1: Number of Moves VS Number of disks

In Graph 2 we will use the Graph 1 and insert the formula TN = 3n – 1 in order to check whether our derivation for the formula of Tower of Hanoi to find the longest moves using non-repetitive steps.. Graph2: Number of Moves VS Number of disks with Function TN = 3n – 1

From Graph 2 we see that the function of TN = 3n – 1 is fitting in all the data points which implies that to find the longest number of non-repetitive steps in any N number of disks can be found out using TN = 3n – 1. It has already found out that it takes approximately 585 billion years to complete moving all the 64 disks in minimum number of moves. Now I will find the time to move all the 64 disks in maximum number of moves using non repetitive steps:

First I will the number of moves it takes:

=T64 = 364 – 1

=3.43368382 × 1030

If one move is equal to one second one then total number moves per year is:

=(60×60×24×365)

Therefore total number of years to move these 64 disks is:

3.43368382 × 1030 = (60×60×24×365)

= 1.088813997 × 1023 = 1.1×1023 years CONCLUSION: The aim of this investigation was to find the longest amount of time for the legend of Hanoi using non-repetitive steps. Initially we formed the recurrence relation to form TN = 3TN-1 + 2 in order to obtain total number of moves for n disks. After these using simultaneous equations we were able to acquire the formula TN = 3n – 1 which was verified using the graph. From this formula, in our modification of tower of Hanoi rules we were able to determine the largest amount of time taken by taking as many moves as possible without repeating any previous configuration of the rings for the 64 disks in the legend of Hanoi.

Bibliography:  A.Bogomolny, Tower of Hanoi, the Hard Way from Interactive Mathematics Miscellany and Puzzles http://www.cut-the-knot.org/recurrence/LongHanoi.shtml, Accessed 06 November 2014  Tower of Hanoi. (2014, June 11). Retrieved October 29, 2014.  Weisstein, Eric W. "Recurrence Equation." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RecurrenceEquation.html  Nykamp DQ, “Recurrence relation definition.” From Math Insight. http://mathinsight.org/recurrence_relation_definition  Tower of Hanoi. (n.d.). Retrieved November 2, 2014, from http://www.sparknotes.com/cs/recursion/examples/section6.rhtml  Math Forum: Ask Dr. Math FAQ: Tower of Hanoi. (n.d.). Retrieved October 29, 2014, from http://mathforum.org/dr.math/faq/faq.tower.hanoi.html  Retrieved October 29, 2014, from https://www.cs.duke.edu/~reif/courses/alglectures/skiena.lectures/ lecture3.pdf  towers of hanoi. (n.d.). The Free On-line Dictionary of Computing. Retrieved November 1, 2014, from Dictionary.com website:http://dictionary.reference.com/browse/towers of hanoi