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