Slide 1Slide 2How to play the 9 stone game?Magic Square: Brought to humanity on the back of a tortoise from the river Lo in the days of Emperor Yu in ancient ChinaMagic Square: Any 3 in a vertical, horizontal, or diagonal line add up to 15.Conversely, any 3 that add to 15 must be on a line.TIC-TAC-TOE on a Magic Square Represents The Nine Stone Game Alternate taking squares 1-9. Get 3 in a row to win.Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 6615-251Great Theoretical Ideas in Computer ScienceLecture 3 (August 31, 2010)Ancient Wisdom: Unary and BinaryHow to play the 9 stone game?9 stones, numbered 1-9 Two players alternate moves. Each move a player gets to take a new stoneAny subset of 3 stones adding to 15, wins.123456789Magic Square: Brought to humanity on the back of a tortoise from the river Lo in the days of Emperor Yu in ancient China492357816Magic Square: Any 3 in a vertical, horizontal, or diagonal line add up to 15.449922335577881166Conversely, any 3 that add to 15 must be on a line.449922335577881166449922335577881166TIC-TAC-TOE on a Magic SquareRepresents The Nine Stone GameAlternate taking squares 1-9. Get 3 in a row to win.Always seek the more useful one!Don’t stick with the representation in which you encounter problems!This idea requires a lot of practiceBasic Idea of this Lecture1234Prehistoric UnaryYou already used induction to verify that the answer is ½n(n+1) Consider the problem of finding a formula for the sum of the first n numbers1 + 2 3 n-1 n S+ + … + + =1+2…n-1n S++n-2++ =n+1+n+1…n+1n+1 2S++n+1++ =n(n+1) = 2SS = n(n+1)21 + 2 3 n-1 n S+ + … + + =1+2…n-1n S++n-2++ =n(n+1) = 2S 1 2 . . . . . . . . n n . . . . . . . 2 1There are n(n+1) dots in the grid!S = n(n+1)2nth Triangular Numbern = 1 + 2 + 3 + . . . + n-1 + n= n(n+1)/2nth Square Numbern = n2= n + n-1Breaking a square up in a new wayBreaking a square up in a new way 1Breaking a square up in a new way 1 + 3Breaking a square up in a new way 1 + 3 + 5Breaking a square up in a new way 1 + 3 + 5 + 7Breaking a square up in a new way 1 + 3 + 5 + 7 + 91 + 3 + 5 + 7 + 9 = 52Breaking a square up in a new wayPythagoras The sum of the first n odd numbers is n2Here is an alternative dot proof of the same sum….n = n + n-1 = n2nth Square Numbern = n + n-1 = n2nth Square Numbern = n + n-1 nth Square Numbern = n + n-1 = Sum of first n odd numbersnth Square NumbernnArea of square = (n)2n-1n-1nnArea of square = (n)2n-1n-1??nnArea of square = (n)2n-1n-1nnnnArea of square = (n)2n-1n-1nnnnArea of square = (n)2n-1n-1nnnn(n-1)2nn-1nnArea of square = (n)2= (n-1)2 + nn-1 + nn= (n-1)2 + n(n-1 + n)= (n-1)2 + n(n)= (n-1)2 + n3(n)2 = n3 + (n-1)2= n3 + (n-1)3 + (n-2)2= n3 + (n-1)3 + (n-2)3 + (n-3)2= n3 + (n-1)3 + (n-2)3 + … + 13(n)2 = 13 + 23 + 33 + … + n3 = [ n(n+1)/2 ]2Can you find a formula for the sum of the first n squares? Babylonians needed this sum to compute the number of blocks in their pyramidsA 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 7Rhind PapyrusScribe Ahmes was Martin Gardener of his day!1 + X1 + X2 + X3 + … + Xn-2 + Xn-1 = X - 1 Xn – 1We’ll use this fundamental sum again and again:The Geometric SeriesA 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 = X - 1 Xn – 1(when x ≠ 1)1 + X1 + X2 + X3 + … + Xn-2 + Xn-1 = X - 1 Xn – 1(when x ≠ 1)1 + 21 +22 + 23 + … + 2n-1 = 2n -1Geometric Series for X=2 21 +22 + 23 + … + 2n = 2n+1 - 21 + X1 + X2 + X3 + … + Xn-2 + Xn-1 = X - 1 Xn – 1(when x ≠ 1)Geometric Series for X=½ 1 + ½ + ½2 + ½3 + … + ½n-1A Similar Suman + an-1b1 +an-2b2 + + … + a1bn-1 + bnA slightly different one0.20 + 1.21 +2.22 + 3.23 + … + n2n = ?S = 0.20 + 1.21 +2.22 + 3.23 + … + n2n 2S = 0.21 +1.22 + 2.23 + 3.24 + … + (n-1)2n + n.2n+1 ––S = 0.20 + 1.21 +1.22 + 1.23 + 1.24 + … + 1.2n – n.2n+1 2n+1 - 2 –S = 2n+1 - 2 – n.2n+1 = – 2n+1 (n-1) – 2S = 2n+1 (n-1) + 2Check Your Work!We’re claiming: S = 2n+1 (n-1) + 20.20 + 1.21 +2.22 + 3.23 + … + n2n = SWhat is S + (n+1)2n+1 ?2n+1 (n-1) + 2 + (n+1)2n+1 = 2n+1 (2n) + 2= 2n+2 (n) + 2= 2(n+1)+1 ((n+1)-1) + 2Also, for n=0both are 0.Two Case StudiesBases and RepresentationBASE X RepresentationS = an-1 an-2 … a1 a0 represents the number: Base 2 [Binary Notation]101 represents:1 (2)2 + 0 (21) + 1 (20)Base 7015 represents:0 (7)2 + 1 (71) + 5 (70)==an-1 Xn-1 + an-2 Xn-2 + . . . + a0 X0Sumerian-Babylonian: 10, 60, 360Egyptians: 3, 7, 10, 60Maya: 20Africans: 5, 10French: 10, 20English: 10, 12, 20Bases In Different CulturesBASE X Representation S = ( an-1 an-2 … a1 a0 )X represents the number:an-1 Xn-1 + an-2 Xn-2 + . . . + a0 X0Largest number representable in base-X 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)k uses log2k + 1 digits in base 2Fundamental Theorem For BinaryEach of the numbers from 0 to 2n-1is uniquely represented by an n-bit number in binaryk uses logXk + 1 digits in base XFundamental Theorem For Base-XEach of the numbers from 0 to Xn-1 is uniquely represented by an n-“digit” number in base Xn has length n in unary, but has length log2n + 1 in binaryUnary is exponentially longer than binaryOther Representations:Egyptian Base …
View Full Document
Unlocking...