Transcript Tower of Hanoi - Suffolk Maths

The Tower of Hanoi
In the temple of Banares, says he, beneath the dome which
marks the centre of the World, rests a brass plate in which
are placed 3 diamond needles, each a cubit high and as thick
as the body of a bee. On one of these needles, at the
creation, god placed 64 discs of pure gold, the largest disc
resting on the brass plate and the others getting smaller and
smaller up to the top one. This is the tower of brahma. Day
and night unceasingly the priests transfer the discs from one
diamond needle to another according to the fixed and
immutable laws of brahma, which require that the priest on
duty must not move more than one disc at a time and that he
must place this disc on a needle so that there is no smaller
disc below it. When the 64 discs shall have been thus
transferred from the needle on which at the creation god
placed them to one of the other needles, tower, temple and
Brahmans alike will crumble into dust and with a thunder clap
the world will vanish.
Edouard Lucas (1884) Probably
The Tower of
Hanoi
5 Tower
A
Illegal Move
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
3 Tower
A
Demo 3
tower
B
C
The Tower of Hanoi
3 Tower
A
B
C
The Tower of Hanoi
3 Tower
A
B
C
The Tower of Hanoi
3 Tower
A
B
C
The Tower of Hanoi
3 Tower
A
B
C
The Tower of Hanoi
3 Tower
A
B
C
The Tower of Hanoi
3 Tower
A
B
C
The Tower of Hanoi
3 Tower
7 Moves
A
B
C
The Tower of Hanoi
•Confirm that you can move a 3 tower to another peg in a minimum
of 7 moves.
•Investigate the minimum number of moves required to move
different sized towers to another peg.
•Try to devise a recording system that helps you keep track of
the position of the discs in each tower.
•Try to get a feel for how the individual discs move. A good way to
start is to learn how to move a 3 tower from any peg to another
of your choice in the minimum number of 7 moves.
•Record moves for each tower, tabulate results look for patterns
make predictions (conjecture) about the minimum number of
moves for larger towers, 8, 9, 10,……64 discs. Justification is
needed.
•How many moves for n disks?
Investigation
The Tower of Hanoi
4 Tower
A
4 Tower show
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
A
B
C
The Tower of Hanoi
4 Tower
15 Moves
A
B
C
The Tower of Hanoi
5 Tower
A
5 Tower show
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
A
B
C
The Tower of Hanoi
5 Tower
31 Moves
A
B
C
The Tower of Hanoi
Discs
Moves
1
1
2
3
3
7
4
15
5
31
6
63
7
127
8
255
64
264? -1
n
2n?- 1
Un = 2Un-1 + 1
This is called a
recursive function.
Why does it happen?
Can you find a way to write
this indexed number out in
full?
How long would it take at a
rate of 1 disc/second?
Results Table
Can you use your calculator and knowledge of the
laws of indices to work out 264?
264
=
232
x
232
4294967296
x
4294967296
2 5 7 6 9 8 0 3 7 7 6
3 8 6 5 4 7 0 5 6 6 4 0
8 5 8 9 9 3 4 5 9 2 0 0
3 0 0 6 4 7 7 1 0 7 2 0 0 0
2 5 7 6 9 8 0 3 7 7 6 0 0 0 0
3 8 6 5 4 7 0 5 6 6 4 0 0 0 0 0
1 7 1 7 9 8 6 9 1 8 4 0 0 0 0 0 0
3 8 6 5 4 7 0 5 6 6 4 0 0 0 0 0 0 0
8 5 8 9 9 3 4 5 9 2 0 0 0 0 0 0 0 0
1 7 1 7 9 8 6 9 1 8 4 0 0 0 0 0 0 0 0 0
264 – 1 =
1 8 4 4 6 7 4 4 0 7 3 7 0 9 5 5 1 6 1 65
Trillions
Billions
Millions
18446744073709551615
Moves needed to transfer all 64 discs.
How long would it take if 1 disc/second was moved?
264  1
 5.85x 1011 years
(60x 60x 24x 365)
 585 000 000 000 years
Seconds in a year.
The age of the Universe is currently put at between
15 and 20 000 000 000 years.
The Tower of Hanoi
Discs
Moves
1
1
2
3
3
7
4
15
5
31
6
63
7
127
8
255
n
2n - 1
This is called a
recursive function.
Un = 2Un-1 + 1
The proof depends first on
proving that the recursive
function above is true for all n.
Then using a technique called
mathematical induction. This is
quite a difficult type of proof to
learn so I have decided to leave it
out. There is nothing stopping you
researching it though if you are
interested.
We can never be absolutely certain that the minimum number of
moves m(n) = 2n – 1 unless we prove it. How do we know for sure that
the rule will not fail at some future value of n? If it did then this
Results Table
would be a counter example to the rule and would disprove it.
2
1
6
3
5
4
Points
Regions
2
2
3
4
4
8
5
n
16
2n-1
6
31
A counter example!
Historical Note
Edouard Lucas
(1842-1891)
The Tower of Hanoi was invented by the French
mathematician Edouard Lucas and sold as a toy in 1883.
It originally bore the name of”Prof.Claus” of the college
of “Li-Sou-Stain”, but these were soon discovered to be
anagrams for “Prof.Lucas” of the college of “Saint
Loius”, the university where he worked in Paris.
Lucas studied the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21,… (named
after the medieval mathematician, Leonardo of Pisa). Lucas may have
been the first person to derive the famous formula for the nth term
of this sequence involving the Golden Ratio: 1.61803… ½(1 + 5).
Lucas/Binet
formula
Fn 
(1  5)n  (1  5)n
2n 5
(1180-1250)
Lucas also has his own related sequence named after him: 2,1,3,4,7,11,… He
went on to devise methods for testing the primality of large numbers and
in 1876 he proved that the Mersenne number 2127 – 1 was prime. This
remains the largest prime ever found without the aid of a computer.
2127 – 1 = 170,141,183,460,469,231,731,687,303,715,884,105,727
Histori
cal
Note
The King’s Chessboard
According to an old legend King Shirham of India wanted to
reward his servant Sissa Ban Dahir for inventing and presenting
him with the game of chess. The desire of his servant seemed
very modest: “Give me a grain of wheat to put on the first
square of this chessboard, and two grains to put on the second
square, and four grains to put on the third, and eight grains to
put on the fourth and so on, doubling for each successive
square, give me enough grain to cover all 64 squares.”
“You don’t ask for much, oh my faithful servant” exclaimed the
king. Your wish will certainly be granted.
Based on an extract from “One, Two, Three…Infinity, Dover Publications.
Kings
Chessboard
How many grains of wheat are on the chessboard?
1
1
2
2
3
4
4
8
5
16
6
32
7
64
nth 2n-1
64
2
-1
The King has
a problem.
The sum of all the grains is:
Sn= 20 + 21 + 22 + 23 + ………….+ 2n-2 + 2n-1
We need a formula for the sum of this Geometric series.
If Sn= 20 + 21 + 22 + 23 + ………….+ 2n-2 + 2n-1
2Sn= ?21 + 22 + 23 + 24 + ………….+ 2n-1 + 2n
2Sn – Sn= ?2n - 20
Sn= 2n - 1
Large
numbers
Reading Large Numbers
The numbers given below are the original (British) definitions which are
based on powers of a thousand. They are easier to remember however if you
write them as powers of a million. They are mostly obsolete these days as the
American definitions (smaller) apply in most cases.
Million
1 000 0001 = 1 000 000 = 106
Billion*
1 000 0002 = 1000 000 000 000 = 1012 (American Trillion)
Trillion
1 000 0003 = 1 000 000 000 000 000 000 = 10 18
Quadrillion
1 000 0004 = 1 000 000 000 000 000 000 000 000 = 10 24
Quintillion
1 000 0005 = 1 000 000 000 000 000 000 000 000 000 000 = 10 30
Sextillion
1 000 0006 = 1036
Septillion
0007
1 000
=
1042
Googol  10
100
10100
Googolplex  10
Upper limit
of a
scientific
calculator.
* The American billion is = 1 000 000 000 and is the one in common usage. A
world population of 6.4 billion means 6 400 000 000.
Reading very large numbers
Edouard Lucas
(1842-1891)
S
To read a very large number simply section off
in groups of 6 from the right and apply Bi, Tri,
Quad, Quint, Sext, etc.
Q
Q
T
B
M
2127 – 1 = 170 141 183 460 469 231 731 687 303 715 884 105 727
One hundred and seventy sextillion,
one hundred and forty one thousand, one hundred and eighty three quintillion,
four hundred and sixty thousand, four hundred and sixty nine quadrillion,
two hundred and thirty one thousand, seven hundred and thirty one trillion,
six hundred and eighty seven thousand, three hundred and three billion,
seven hundred and fifteen thousand, eight hundred and eighty four million,
one hundred and five thousand, seven hundred and twenty seven.
Reading very large numbers
To read a very large number simply section off in groups of 6
from the right and apply Bi, Tri, Quad, Quint, Sext, etc.
Try some of these
M
Q
B
T
41 183 460 385 231 191 687 317 716 884
Q
Q
M
T
B
57 786 765 432 167 876 564 875 432 897 675 432
Q
Q
T
S
M
B
9 412 675 987 453 256 645 321 786 765 786 444 329 576
Q
S
Q
T
M
B
S
678 876 543 786 543 987 579 953 237 896 764 345 675 876 453 231
How big is a Googol?
Googol  10
100
Upper limit
of a
scientific
calculator.
10 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000.
1 followed by 100 zeros
The googol was introduced to the world by the American
mathematician Edward Kasner (1878-1955). The story goes that
when he asked his 8 year old nephew, Milton, what name he
would like to give to a really large number, he replied “googol”.
Kasner also defined the Googolplex as 10googol, that is 1 followed
by a googol of zeros.
Do we need a number this large? Does it have any physical meaning?
Google
How big is a Googol?
Googol  10100
10 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000 000 000 000 000 000
000 000 000 000 000 000.
1 followed by 100 zeros
We saw how big 264 was when we converted that many seconds
to years:  585 000 000 000 years. What about a googol of
seconds? Who many times bigger is a googol than 264? Use your
scientific calculator to get an approximation.
100
10
80

5.4
x
10
264
Google
So  5.4 x 1080 x 5.85x 1011
 3x 1092 years.
How big is a Googol?
Googol  10
100
Upper limit
of a
scientific
calculator.
10 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000 000 000
000 000 000 000 000 000 000.
Supposing that the Earth was composed
solely of the lightest of all atoms
(Hydrogen), how many would be
contained within the planet?
Earth Mass = 5.98 x 1027 g
5.98x 1027
51

3.58
x
10
 Googol
24
1.67x 10
The total number of a atoms in the
universe has been estimated at 1080.
Hydrogen atom
Mass = 1.67 x 10-24g
Is there a quantity as large as a Googol?
Find all possible arrangements for the sets of numbered cards below.
1
1 2
1 2 3
1
1, 2
3, 1, 2
1
2, 1
2
Can you write the number of
arrangements as a product of
successive integers?
4, 3, 1, 2
4, 1, 2, 3
4, 2, 3, 1
1, 3, 2
1, 2, 3
3, 4, 1, 2
1, 4, 2, 3
2, 4, 3, 1
3, 1, 4, 2
1, 2, 4, 3
2, 3, 4, 1
3, 2, 1
3, 1, 2, 4
1, 2, 3, 4
2, 3, 1, 4
4, 1, 3, 2
4, 3, 2, 1
4, 2, 1, 3
1, 4, 3, 2
3, 4, 2, 1
2, 4, 1, 3
1, 3, 4, 2
1, 3, 2, 4
3, 2, 4, 1
3, 2, 1, 4
2, 1, 4, 3
2, 3, 1
2, 1, 3
Objects
arrangements
n!
1
1
1
2
2
2x1
3
6
3x2x1
4
24
4x3x2x1
5
120
5x4x3x2x1
Factorials
1 2 3 4
6
2, 1, 3, 4
What about if 5 is introduced.Can
24 you see what will happen?
n! is read as n factorial).
1 2 3 4 5
120
Is there a quantity as large as a Googol?
The number of possible arrangements of a set of n objects is given
by n! (n factorial). As the number of objects increase the number
of arrangements grows very rapidly.
How many arrangements are there
for the books on this shelf?
8! = 40 320
How many arrangements are there
for a suit in a deck of cards?
13! = 6 227 020 800
Is there a quantity as large as a Googol?
The number of possible arrangements of a set of n objects is given
by n!.(n factorial) As the number of objects increases the number
of arrangements grows very rapidly.
16 3 2 13
5 10 11 8
How many arrangements are there for
placing the numbers 1 to 16 in the grid?
9 6
7 12
4 15 14 1
16! = 2.1 x 1013
ABCDEFGHIJKLMNOPQRSTUVWXYZ
How many arrangements are there
for the letters of the Alphabet?
26! = 4 x 1026
Is there a quantity as large as a Googol?
The number of possible arrangements of a set of n objects is given
by n!.(n factorial) As the number of objects increases the number
of arrangements grows very rapidly.
Find other factorial values on your calculator. What is the
largest value that the calculator can display?
20!
2.4 x 1018
30!
2.7 x 1032
40!
8.2 x 1047
50!
3.0 x 1064
52!
8.1 x 1067
60!
8.3 x 1081
69!
1.7 x 1098
70!
Error
70!  10100 = Googol
So although a googol of physical
objects does not exist, if you
hold 70 numbered cards in your
hand you could theoretically
arrange them in a googol number
of ways. (An infinite amount of
time of course would be needed).
What about a Googolplex?
A Googolplex  10
A number so big that it can
never be written out in full!
There isn’t enough ink,time
or paper.
googol
 10
2
1010  1 with a 100 zeros (a googol)
103
 1 with a 1000 zeros
106
 1 with a 1 000 000 zeros
10
10
1012
10
The table shown gives
you a feel for how
truly unimaginable this
number is!
10100
 1 with a 1 billion zeros
18
1010  1 with a 1 trillion zeros
1024
 1 with a quadrillion zeros
1030
 1 with a quintillion zeros
1036
 1 with a sextilion zeros
10
10
10
42
1010  1 with a septilion zeros
100
1010
Googolplex
 1 with a googol zeros
And
Finally
2000 digits on a page.
How many pages needed?
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000………………….
10100
A Googolplex  10
 1 followed by 10100 zeros .
10100
96
Pages needed 

5
x
10
2x 103
The End!
The Tower of Hanoi
In the temple of Banares, says he, beneath the dome which
marks the centre of the World, rests a brass plate in which
are placed 3 diamond needles, each a cubit high and as thick
as the body of a bee. On one of these needles, at the
creation, god placed 64 discs of pure gold, the largest disc
resting on the brass plate and the others getting smaller and
smaller up to the top one. This is the tower of brahma. Day
and night unceasingly the priests transfer the discs from one
diamond needle to another according to the fixed and
immutable laws of brahma, which require that the priest on
duty must not move more than one disc at a time and that he
must place this disc on a needle so that there is no smaller
disc below it. When the 64 discs shall have been thus
transferred from the needle on which at the creation god
placed them to one of the other needles, tower, temple and
Brahmans alike will crumble into dust and with a thunder clap
the world will vanish.
Worksheets
The Tower of Hanoi
A
B
C
Tower of Hanoi
•Confirm that you can move a 3 tower to another peg in a minimum
of 7 moves.
•Investigate the minimum number of moves required to move
different sized towers to another peg.
•Try to devise a recording system that helps you keep track of
the position of the discs in each tower.
•Try to get a feel for how the individual discs move. A good way to
start is to learn how to move a 3 tower from any peg to another
of your choice in the minimum number of 7 moves.
•Record moves for each tower, tabulate results look for patterns
make predictions (conjecture) about the minimum number of
moves for larger towers, 8, 9, 10,……64 discs. Justification is
needed.
•How many moves for n disks?
2
1
Points
2
3
4
5
n
3
5
4
Regions
Reading very large numbers
To read a very large number simply section off in groups of 6
from the right and apply Bi, Tri, Quad, Quint, Sext, etc.
Try some of these
41 183 460 385 231 191 687 317 716 884
57 786 765 432 167 876 564 875 432 897 675 432
9 412 675 987 453 256 645 321 786 765 786 444 329 576
678 876 543 786 543 987 579 953 237 896 764 345 675 876 453 231