### Towers of Hanoi

The aim of this piece of coursework is to complete different investigations. The name of these investigations is the Towers Of Hanoi. I will need to be patient and enthusiastic to complete these testing challenges. Basically I have 4 discs of decreasing radii and 3 towers named A, B and C. I am allowed to move only one disc at a time and I cannot place a larger disc on top of a smaller disc. I have to complete the challenges within a certain amount of goes. I will do 6 investigations using 1, 2, 3, 4, 5 and 6 discs. After I have completed these investigations I will compare them and try to find patterns etc. I will be required to show diagrams, graphs, tables of results and rules. I will also include a conclusion.Investigating some challengesNow I am going to show my the 6 investigations and try to find patterns and rules afterwardsInvestigation 1In my first investigation I will attempt to successfully move 4 discs to tower C in the least number of moves.I will now confirm that with four discs it is possible to get from the start (A) to the finish (B) or (C) in a minimum of 15 moves.This is the position I will begin my challenge from.1) 2)3) 4)5) 6)7) 8)9) 10)11) 12)13) 14)15)Moves: 1-B2-C1-C3-B1-A2-B1-B4-C1-C2-A1-A3-C1-B2-C1-CAs I confirmed, it is possible to complete this task in a minimum of 15 moves.Investigation 2In my second investigation I am going to try to successfully move one disc from the start (A) to the finish (B or C).PredictionI predict that it will take me one move to get from start to finish as there’s only one disc and so I can move it anywhere I want in one move as there are no other discs.This is the position I am going to start from.1)Moves: 1-CMy prediction was correct and I now can confirm it takes me 1 move to successfully move 1 disc from start to finish.Investigation 3Now I am going to try to successfully move 2 discs from start (A) to finish (B or C) in the least number of moves possible.This is the position I am going to start my challenge form.1) 2)3)Moves: 1-B2-C1-CMy challenge was successful and I completed it in 3 moves.Investigation 4Now in my fourth investigation I am going to attempt to move 3 discs from start (A) to finish (B or C) in the minimum amount of moves possible.The position I am going start from is at the bottom of the last page.1) 2)3) 4)5) 6)7)Moves: 1-C2-B1-B3-C1-A2-C1-CMy challenge was successful as I moved 4 discs from start (A) to finish (B) or (C.)Investigation 5Now in my fifth investigation I am going to attempt to move 5 discs from start (A) to finish (B or C.)Moves: 1-B2-C1-C3-B1-A2-B1-B4-C1-C2-A1-A3-C1-B2-C1-C5-C1-A2-C1-C3-A1-B2-A1-A4-C1-C2-B1-B3-C1-A2-C1-CMy challenge was successful as I moved the 5 discs from start (A) to the finish (B or C.) I looked for a pattern and noticed the difference between the number of moves for the different number of discs is doubled.Here’s the table of results so far: -Number discsNumber of moves112337415531As we can see the difference between the number of moves 1 and 3 is 2 and then between 3 and 7 is 4. Here we can see the number has doubled. The difference between 7 and 15 is 8 (the number has again doubled) and the number of moves again doubles between 15 and 31, as it is 16. Now I can predict how many moves it will take for 6 discs to get from the start (A) to the finish (B or C).Investigation 6I will now investigate the sixth challenge and I will try to successfully move 6 discs from the start (A) to the finish (B or C.)PredictionI can now predict the number of moves that it will take me to move all 6 discs from start to finish.Here is the pattern I am going to use: -2 x 1 – 1 = 12 x 2 – 1 = 32 x 2 x 2 -1 = 72 x 2 x 2x 2 – 1 = 152 x 2 x 2 x 2 x 2 -1 = 312 x 2 x 2 x 2 x 2 x 2 – 1 = 63Moves: 1-B2-C1-C3-B1-A2-B1-B4-C1-C2-A1-A3-C1-B2-C1-C5-C1-A2-C1-C3-A1-B2-A1-A4-C1-C2-B1-B3-C1-A2-C1-C6-C1-C2-A1-A3-C1-B2-C1-C4-A1-A2-B1-B3-A1-C2-A1-A5-C1-B2-C1-C3-B1-A2-B1-B4-C1-C2-A1-A3-C1-B2-C1-CMy prediction is correct and so it is possible to move all 6 discs from start to finish in a minimum of 63 moves, which also confirms that my pattern works. This enables me to work out the number of moves it will take for any number of discs. This now means I can now construct a formula, which I will do later on in my results.Table Of ResultsNumber Of DiscsNumber Of Moves112337415531663This table of results clearly shows us the results we found and also the table is quite easy to understand and read.Looking for a patternThe pattern I found was that the difference between the number of moves doubles each tome. For example between 1 and 3 the number is 2, then between 3 and 7 the number is 4 and between 7 and 15 is 8 and so on the pattern continues.2 x 1 = 22 x 2 = 42 x 4 = 82 x 8 = 162 x 16 = 322 x 32 = 642 x 64 = 128This pattern enables me to predict the next number as all I do is add the doubled number onto the last number of moves. For example for 6 discs the number of moves taken were 63 and so I can add on 64 to 63 and I get the number of moves needed to complete 7 discs.Graph of resultsThis graph will be on the next page.Finding a rule and checking itI found 2 types of rules which work and are successful.1) Position to term rule:This is a rule which enables me to predict the amount of moves it will take for any number of discs. The rule is 2n-1. This rule works by me multiplying the number by itself by different numbers and then subtracting 1 each time.E.g.: -2 -1 = 12 x 2 – 1 = 32 x 2 x 2 – 1 =72 x 2 x 2 x 2 – 1 = 152 x 2 x 2 x 2 x 2 – 1 = 312 x 2 x 2 x 2 x 2 x 2 – 1 = 632 x 2 x 2 x 2 x 2 x 2 x 2 – 1 = 1272 x 2 x 2 x 2 x 2 x 2 x 2 x 2 – 1 = 2552 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 -1 = 511As you can see all these sums work and I could carry on using the formula.2) Term to term rule:This is a rule which enables me to find the amount of moves required for any number of discs. The rule is 2n+1. All I do is double the last term, For example: -2 x 0 +1 = 12 x 1 +1 = 32 x 3 +1 = 72 x 7 +1 = 152 x 15 +1 = 312 x 31 +1 = 632 x 63 +1 = 1272 x 127 +1 = 2552 x 255 +1 = 5112 x 511 +1 = 1023As you can see the rule works well and so is very helpful in finding the next trem along. All you do is double the last term like double the 3 and +1 you get 7 and then you do the same again.ConclusionWhat I discovered is that there are simple ways of solving these investigations. These patterns and rules were really helpful in the end for my work as when I was trying to crack one of the puzzles I knew how many moves I had to do it in which help. I knew this due to the patterns I found and the rules. The 2 rules I found were the 2n-1 rule, which is a position to term rule, and the other rule, which is the term-to-term rule, is 2n+1. Overall I found that finding the rules and patterns came quite easily in the end as the patterns built up as I done more work.