Queen Elizabeth Grammar School Essays

Queen Elizabeth Grammar School Essays Queen Elizabeth Grammar School Essay Queen Elizabeth Grammar School Essay The Towers of Hanoi is an ancient mathematical game. The aim of this coursework is to try to identify patterns and rules associated with the game and explain them in mathematical terms. The definitions and rules are: Rules: * There are only three positions a disc can be placed. Poles A, B or C. * A disc can only go on top of a larger one. (I.e. Disc A can only go on top of Discs B and C, but Disc B cannot go on top of disc A) * The object of the game is to get all the discs to move from pole A to pole B of C in the least number of moves. * Only one disc may be moved at a time. Finding Formula A Number Of Discs Least Number Of Moves Previous term (Doubled) 1 1 2 3 2 3 7 6 4 15 14 5 31 30 6 63 62 7 127 126 8 255 254 From looking at the table it is quite clear that there is a pattern linking the number of discs and the least number of moves. It is clear that there is an element of doubling involved, as the least number of moves nearly doubles each time. When I add the extra column see above, it is clear that there is a doubling element involved. When I look again, I can see that the pattern is the previous term doubled plus 1. This can be expressed mathematically as: Un = 2(Un-1) +1 This can be shown in: 1. For 1 disc, it takes 1 move to move disc A from pole 1 to pole 3; 2. For 2 discs, it takes 3 moves: 2(Un-1) +1 = 2(1) + 1 = 3 3. For 3 discs, it takes 7 moves: 2(Un-1) +1= 2(3) + 1 = 7 4. For 4 discs, it takes 15 moves: 2(Un-1) +1= 2(7) + 1 = 15 5. For 5 discs, it takes 31 moves: 2(Un-1) +1= 2(15) + 1 = 31 To understand how this works, coding is needed to see how a disc moves individually. Coding should show me the patterns involved and then I should be able to justify my formula based on this. Coding is on the next page. Coding Number of Discs: 2 3 4 5 Disc Moving: A A A A B B B B A A A A C C C A A A B B B A A A D D A A B B A A C C A A B B A A E A B A C A B A D A B A C A B A From my coding it is now clearer why that formula is that particular formula. It can be seen that there is symmetry involved in each pattern. The symmetry is always about the name of the bottom disc. I.e. with 3 discs the symmetry is about disc C and this is the bottom disc From the coding, I can also see that the pattern of moves for 2 discs is present in the beginning of 3 discs, 4 discs etc. The pattern for 3 discs is also in the pattern for 4 discs and so on. This is can therefore be explained as: In n number of discs where n is greater than 2, the first three moves will always be ABA. This is because the n-1 discs pattern is included in the n pattern. We have (Un-1), because we take into account the previous terms pattern when making the next tower. We have the 2 term because this pattern is repeated twice, firstly to deconstruct the tower and then to rebuild the tower on top of the bottom disc. We have the +1 term because this is where the bottom disc moves from Pole A to Poles B or C. This can be demonstrated when we move three tiles. ABA This is the move pattern for 2 tiles (Un-1). This allows C to be able to move. C This is when the bottom tile moves and we therefore get the +1 from. ABA This is where the doubling element comes in as well as the n-1 discs moves pattern. This is where the tower is rebuilt on top of disc C. So overall, we get the formula: 2(Un-1) +1 There are limitations to this however. Un-1 has to be an integer because we cannot have 3.5 moves. Un-1 has to also be equal to or greater than 0 and has to be an integer because the formula wouldnt work as the result would be negative and we cannot have a negative number of moves. Formula B Finding the formula that shows how many times a certain disc moves From formula A I now have a basis on which to work. Given a certain number of discs I need to be able to say how many times a desired disc moves. Firstly, I need to analyze my results from the coding. Disc: Disc A Disc B Disc C Disc D Disc E Disc F Total Number of times each disc moves: 3 Discs 4 2 1 7 4 Discs 8 4 2 1 15 5 Discs 16 8 4 2 1 31 6 Discs 32 16 8 4 2 1 63 We can also once again see a pattern here. There is a doubling, well halving element involved depending on which way you look at it. The table above shows how many times a certain disc moves. Whenever a new disc is added to the sequence, such as in Disc 4, the number of moves for Disc A doubles. I.e. As you go down the table the number of moves for each disc doubles. When I look at the results, I notice that they are all from the 2n pattern. Therefore I can come up with the relationship for the number of times each disc moving being: Number of times a certain disc moves = 2n-d with d being the disc number. So in Disc A, the number for d would be 1, as this is the first disc. Disc B would be 2 etc. In the series for 6 discs, the terms would be Disc A: 2n-d = 26-1 = 32 Disc B: 2n-d = 26-2 = 16 Disc C: 2n-d = 26-3 = 8 Disc D: 2n-d = 26-4 = 4 Disc E: 2n-d = 26-5 = 2 Disc F: 2n-d = 26-6 = 1 This therefore works. Now I have to prove that this works. We can see that Disc B always moves half as many times as Disc A. If we do 2n we get how many times Disc A Moves always. If we do 2n-2 we get how many times disc B moves always. This is because as we take more away from 2n we get smaller and smaller until it ultimately converges to 0. Taking 1 away from this halves the number of moves; whereas taking 2 away quarters the number of moves. Disc B always moves less times than Disc A because of the recurring pattern. A has to move more times, because it has to keep going on top of the larger tiles as the rules state. A has more options to move than B because it is smaller. There are limitations to this however, because we cannot have d being greater than n because the formula would not work. It wouldnt work because we cannot have half of a move or a quarter of a move. We cannot also have n being less than 1 because of the same principal. The number of moves and the disc number have to also be an integer because we cannot have Disc A moving 3.5 times. The Link The series above is a geometric series. I know this because the difference is different each time. The general way to write a geometric series is: General: a + ar + ar2 + ar3 + arn-1 The terms: a is the starting number in the sequence. I will use a 6 tiled sequence so my starting number from the table will be 32 as this is the number of times disc A moves. Ratio r This is the amount that a is multiplied to get the next term. So 32 is multiplied by 0.5 to get 16. Our sequence is: S= 32 + 16 + 8 4 +2 +1 To get the sum of a geometric sequence, we need to multiply by the common ratio (0.5) S = a + ar + ar2 + ar3 + + arn-1 rS = a + ar + ar2 + ar3 + +arn-1+ arn S-rS = a arn This can be expressed as S(1-r) = a(1-rn) Divide this by 1-r gives: a(1-rn) S= 1-r Before I can use this information however, I need to determine a formula to get a. I can use the formula I discovered above but just modify it slightly. To get a the formula is: 2n-1 as this is the formula for Disc A always. So the formula above instead of being 2n-d could have also been 2n-1 for the same principals. With n being the disc number you are trying to find. Disc 50 would be 249 and disc 3 would always be 22 and so on. Therefore I can now substitute in my values in a pile of 6 discs to get the formula that links formula A and B. To determine the ratio we have to just see how much the sequence is decreasing each time. 32 + 16+ 8 + 4 + 2 + 1 To get the next term suing the general geometric sequence rule, it says that we have to multiply 32 by a constant. a ar. So: a ar is the same as ar divided by a. 16 = 0.5. This is the ratio. 32 Therefore for the sum of my geometric series, the formula should be: a(1-rn) S= 1-r S = 25(1-0.56) 0.5 S= 31.5 = 63 0.5 Therefore the sum of a 6 termed series is 63. This can be proved by getting the formula for the previous term. S = 24(1-0.55) = 31 0.5 According to my earlier formula (Un = 2(Un-1) +1) when I substitute in I should get the answer 63. 2 x 31 + 1 = 63. This works because of the algebra of the general geometric sequences: S = a + ar +ar2 This is the rule for each term in the sequence: arn-1 or 2n-d I then multiplied by the common ratio (r) rS = ar + ar2 + ar3 This is the rule: arn Then I subtracted the sequence multiplied by the common ratio from the first sequence. This gave: S-rS = a arn = a(1-rn) Therefore S=a(1-rn) (1-r)) Limitations are: S has to be greater than 0 and has to be an integer a has to be positive and an integer r has to be an integer and greater than 0 Extension Work: Finding which pole the pile will be built upon. I have noticed from my work that when I had 3 discs on my pile, disc C landed on where I put disc A to start off with which was on Pole C. When I had 4 discs however, I noticed that the pile finished on where I did not place tile A which was Pole B. This can therefore be expressed as: If the number of discs in the pile to start with is even then the bottom disc will land where you place Disc A to start off with. If the number of discs in the pile is odd however, then the bottom disc in the pile will finish up on the pole where you did not place Disk A. Therefore where you put Disc A can be considered crucial to where you want your pile to land Overview: If I have 25 discs in my pile, I can expect there to be: 33554431 moves involved in the series. Disc A will move 16777216 times; whereas disc y will move only once. The Pile will end up on the pole where you place disc A, so if I leave it on pole B to start with, the pile will end up on Pole B. According to the monks in Hanoi, the world will end in over 500 Million Years. The problems with my investigation: I have realized that there are only 26 letters in the alphabet. With my system of labeling, it is impractical for me to label each disc A, B C etc because I will run out of letters. I will either have to name the poles ABC or call each disc past 26, A1 etc.