Investigating The Towers Of Hanoi Essay, Research Paper
Introduction – I am going to investigate the Hanoi Towers. The objective of the game is to move the discs from position A to positions B or C in the minimum number of moves where in one go you are only allowed to move one disc. I will vary the number of discs and record my results. I will make predictions and look for patterns. I will ultimately aim to find a formula for the number of moves it takes to move the tower from A to B or C. A
B
C
I will know 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
I now know that it is possible to move a tower of 4 discs ina minimum of 15 moves. I will know find the least amount of moves required to complete the game when you start with a tower of 5 discs. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
I now know that it is possible to move a tower of 5 discs in a minimum of 31 moves.
I will know find the least amount of moves required to complete the game when you start with a tower of 2 discs.
1
2
3
I now know that it is possible to move a tower of 2 discs in a minimum of 3 moves.
I will know find the least amount of moves required to complete the game when you start with a tower of 1 discs.
1
I now know that it is possible to move a tower of 1 disc in a minimum of 1 move. I know have 5 results and will put together a table of results. Table of Results
24 816 (32)
As you can see there is no 2 4 8
constant pattern, but a diagonal2 4 8
pattern. 2 4
2 From the top row of differences I can see that the previous term doubled gives the next term in the sequence. Therefore I predict that the next difference would be 32 for a tower of 6 discs (see results table) giving the number of moves as 63 also to back up my prediction I can see that the previous term multiplied by 2 plus 1 gives the next e.g.
1 x 2 + 1 = 3
3 x 2 + 1 = 7
7 x 2 + 1 = 15
15 x 2 + 1 = 31
31 x 2 + 1 = 63 I will know confirm that with six discs it is possible to get from the start to the finish in a minimum of 63 moves.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
I now know that it is possible to move a tower of 6 discs in a minimum of 63 moves. So I can now construct a formula:
The nth term = the previous term doubled, plus one or Tn = 2Tn-1 + 1 eg. 1 Tower 2 x 0 +1 = 1
2 Towers 2 x 1 +1 = 3
3 Towers 2 x 3 +1 = 7
4 Towers2 x 7 +1 = 15
5 Towers2 x 15 +1 = 31
6 Towers2 x 31 +1 = 63
7 Towers2 x 63 +1 = 127
8 Towers2 x 127 +1 = 255
9 Towers2 x 255 +1 = 511
10 Towers 2 x 511 +1 = 1023