15 251 Great Theoretical Ideas in Computer Science Ancient Wisdom Unary and Lecture 3Binary August 31 2010 How to play the 9 stone game 1 2 3 4 5 6 9 7 8 9 stones numbered 1 9 Two players alternate moves Each move a player gets to take a new stone Any subset of 3 stones adding to 15 wins Magic Square Brought to humanity on the back of a tortoise from the river Lo in the days of Emperor Yu in ancient China 4 9 3 2 5 8 7 1 6 Magic Square Any 3 in a vertical horizontal or diagonal line add up to 15 4 9 2 3 5 7 8 1 6 Conversely any 3 that add to 15 must be on a line 4 9 2 3 5 7 8 1 6 TIC TAC TOE on a Magic Square Represents The Nine Stone Game Alternate taking squares 1 9 Get 3 in a row to win 4 9 2 3 5 7 8 1 6 Basic Idea of this Lecture Don t stick with the representation in which you encounter problems Always seek the more useful one This idea requires a lot of practice Prehistoric Unary 1 2 3 4 Consider the problem of finding a formula for the sum of the first n numbers You already used induction to verify that the answer is n n 1 1 2 3 n 1 n S n n 1 n 2 2 1 S n 1 n 1 n 1 n 1 n 1 2S n n 1 2S n n 1 S 2 1 2 3 n 1 n S n n 1 n 2 2 1 S n n 1 2S n n 1 S 2 There are n n 1 dots in the grid n 2 1 1 2 n nth Triangular Number n 1 2 3 n 1 n n n 1 2 nth Square Number n n2 n n 1 Breaking a square up in a new way 1 Breaking a square up in a new way 1 3 Breaking a square up in a new way 1 3 5 Breaking a square up in a new way 1 3 5 7 Breaking a square up in a new way 1 3 5 7 9 Breaking a square up in a new way 1 3 5 7 9 52 Breaking a square up in a new way The sum of the first n odd 2 numbers is n Pythagoras Here is an alternative dot proof of the same sum nth Square Number n n n 1 n2 nth Square Number n n n 1 n2 nth Square Number n n n 1 nth Square Number n n n 1 Sum of first n odd numbers Area of square n 2 n n Area of square n 2 n 1 n 1 n n Area of square n 2 n 1 n 1 n n Area of square n 2 n 1 n 1 n n n n Area of square n 2 n 1 n 1 n n n n Area of square n 2 n 1 2 n n 1 n n n 1 2 n n 1 n n 1 2 n n n 1 n 1 2 n n n 1 n n n n n 1 n 1 2 n3 n n 2 n3 n 1 2 n3 n 1 3 n2 2 n3 n 1 3 n 2 3 n 33 2 n n 1 3 n 2 3 13 n 2 n3 13 23 33 n n 1 2 2 Can you find a formula for the sum of the first n squares Babylonians needed this sum to compute the number of blocks in their pyramids Rhind Papyrus Scribe Ahmes was Martin Gardener of his day A man has 7 houses Each house contains 7 cats Each cat has killed 7 mice Each mouse had eaten 7 ears of spelt Each ear had 7 grains on it What is the total of all of these Sum of powers of 7 1 X1 X2 X3 Xn 2 Xn 1 Xn 1 X 1 We ll use this fundamental sum again and again The Geometric Series A Frequently Arising Calculation X 1 1 X1 X2 X3 Xn 2 Xn 1 A Frequently Arising Calculation X 1 1 X1 X2 X3 Xn 2 Xn 1 X1 X2 X3 Xn 1 Xn 1 X1 X2 X3 Xn 2 Xn 1 Xn 1 1 X1 X2 X3 Xn 2 Xn 1 when x 1 Xn 1 X 1 Geometric Series for X 2 1 21 22 23 2n 1 21 22 23 2n 1 X1 X2 X3 Xn 2 Xn 1 when x 1 2n 1 2n 1 2 Xn 1 X 1 Geometric Series for X 1 2 3 n 1 1 X1 X2 X3 Xn 2 Xn 1 when x 1 Xn 1 X 1 A Similar Sum an an 1b1 an 2b2 a1bn 1 bn A slightly different one 0 20 1 21 2 22 3 23 n2n S 0 20 1 21 2 22 3 23 2S n2n 0 21 1 22 2 23 3 24 n 1 2n n 2n S 0 20 1 21 1 22 1 23 1 24 1 2n 2n 1 2 S 2n 1 2 n 2n 1 2n 1 n 1 2 S 2n 1 n 1 2 n 2n Check Your Work 0 20 1 21 2 22 3 23 n2n S We re claiming S 2n 1 n 1 2 What is S n 1 2n 1 2n 1 n 1 2 n 1 2n 1 2 n 1 2n 2 2n 2 n 2 2 n 1 1 n 1 1 2 Also for n 0 both are 0 Two Case Studies Bases and Representation BASE X Representation S an 1 an 2 a1 a0 represents the number an 1 Xn 1 an 2 Xn 2 a0 X0 Base 2 Binary Notation 101 represents 1 2 2 0 21 1 20 Base 7 015 represents 0 7 2 1 71 5 70 Bases In Different Cultures Sumerian Babylonian 10 60 360 Egyptians 3 7 10 60 Maya 20 Africans 5 10 French 10 20 English 10 12 20 BASE X Representation S an 1 an 2 a1 a0 X represents the number an 1 Xn 1 an 2 Xn 2 a0 X0 Largest number representable in baseX with n digits X 1 X 1 X 1 X 1 X 1 X 1 X X 1 Xn 1 Xn 2 X0 Xn 1 Fundamental Theorem For Binary Each of the numbers from 0 to 2n 1is uniquely represented by an n bit number in binary k uses log2k 1 digits in base 2 Fundamental Theorem For Base X Each of the numbers from 0 to Xn 1 is uniquely represented by an n digit number in base X k uses logXk 1 digits in base X n has length n in unary but has length log2n 1 in binary Unary is exponentially longer than binary Other Representations Egyptian Base 3 Conventional Base 3 Each digit …
View Full Document
Unlocking...