SAMPLE FINAL EXAM 1. Give a concise but precise summary of the proof of the classification of plane symmetric patterns into 17 symmetry types. Answer: Given a plane symmetric pattern we can extract a template, tape together the appropriate edges and thereby view the original pattern as a map of the surface that results. Since the flat plane has no angle defect at any point, neither does the surface we get, provided that we modify the definition of angle defect to take account of gyration points and corner points. Thus the surface will have total angle defect equal 0. Then by the Gauss-Bonnet theorem the surface must have Euler number equal zero. But we can construct any surface by starting with a sphere and adding handles, holes, Mobius strips, cone points and corner points. The sphere has Euler number 2. Adding a handle lowers the Euler number by 2; adding a hole or a Mobius strip lowers the Euler number by 1; adding a cone point of order n lowers the Euler number by (n-1)/n, adding a corner point by (n-1)/2n. A careful enumeration yields only 17 combinations of modifications that lower the Euler number exactly to 0. 2. Identify the symmetry types of the following patterns: a. S S S S S S S S b. S S S S S S S S c. H H H H H H H H d. H H H H H H H H S S S S S S S S S S S S S S S S H H H H H H H H H H H H H H H H S S S S S S S S S S S S S S S S H H H H H H H H H H H H H H H H S S S S S S S S S S S S S S S S H H H H H H H H H H H H H H H H S S S S S S S S S S S S S S S S H H H H H H H H H H H H H H H H S S S S S S S S S S S S S S S S H H H H H H H H H H H H H H H H Answer: a. 2222 b. 2222 c. *2222 d. 2*22 3. a. Compute the continued fraction expansion of the square root of 19 far enough to see a repeating pattern emerge. Answer: 4 + 1 --- 2 + 1 ---- 1 + 1 --- 3 + 1 --- 1 + 1 --- 2 + 1 --- 8 + 1 --- 2 + 1 ---- 1 + 1 --- 3 + 1 --- 1 + 1 --- 2 + 1 --- 8 + ... b. Use the continued fraction expansion of the square root of 19 to find the first six fractions that approximate this irrational number especially well. Answer. 4 2 1 3 1 2 8 ---------------------------------- 0 1 4 9 13 48 61 170 1421 <--- Numerators 1 0 1 2 3 11 14 39 326 <--- Denominators c. Divide the musical octave into equal parts to create a scale that very nearly offers a frequency ratio of 8/5 above and below each tone. x y Answer: We need approximate solutions of 2 = (8/5) . That means we want approximate solutions of y/x = log(2)/log(8/5). The calculator gives log(2)/log(8/5) = 1.4747698473569... This number has continued fraction expansion 1 + 1 --- 2 + 1 --- 9 + 1 --- 2 + ... from which we reconstruct the fractions 1 2 9 2 ---------------- 0 1 1 3 28 59 1 0 1 2 19 40 Dividing the octave into 28 parts gives a practical solution. Then 19/28's of an octave gives a frequency ratio of 19/28 2 = 1.600554..., close enough to 8/5 = 1.6 for the the human ear not to detect the difference. 4. a. Euler discovered that a counting number may be expressed as the sum of distinct (all different) numbers in exactly the same number of ways it can be expressed as the sum of odd numbers. To demonstrate this we can match each expression of a number n as the sum of distinct parts to an expression as a sum of odd parts by repeatedly breaking even parts into equal halves until only odd parts remain. For example 34 = 14 + 12 + 5 + 3 becomes 34 = 7 + 7 + 6 + 6 + 5 + 3 and then finally 31 = 7 + 7 + 3 + 3 + 3 + 3 + 5 + 3 = 7 + 7 + 5 + 3 + 3 + 3 + 3 + 3 . Now you work the process IN REVERSE for the expression 39 = 5 + 5 + 5 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 1 + 1 + 1 Answer: The reverse of splitting even parts into equal halves consists of repeatedly combining equal summands into even parts. We get 39 = 5 + 5 + 5 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 1 + 1 + 1 = 10 + 5 + 6 + 6 + 6 + 3 + 2 + 1 = 10 + 5 + 12 + 6 + 3 + 2 + 1 = 12 + 10 + 6 + 5 + 3 + 2 + 1 b. A crucial step in our juggling site swap bijection uses a bijection that matches permutations of {1, 2, ..., n} with m drops to permutations of {1, 2, ..., n} with m descents using cycle notation. Consider the permutation x 1 2 3 4 5 6 7 8 9 pi(x) 6 3 5 2 4 8 1 9 7 . How many drops does pi have? To what permutation with the same number of descents does the algorithm match it? (Give the permutation in function form.) Answer: The permutation pi has drops from 6 to 3, 5 to 2, 8 to 1 and 9 to 7, for a total of 4. To obtain the cycle notation for a permutation guaranteed to have 4 descents we add parentheses (6 3 5 2 4) (8 1)(9 7) so that the first number that appears in a cycle exceeds all the others. Now we want the permutation with 6 goes to 3 goes to 5 goes to 2 goes to 4 goes to 6; 8 goes to 1 goes to 8; 9 goes to 7 goes to 9. In function form we get 1 2 3 4 5 6 7 8 9 8 4 5 6 2 3 9 1 7 By construction, the list of descents coincides with the original list of drops. 5. Explain why infinite sets can have different sizes. Answer. The set of counting numbers and the set of decimals can't have the same size. If they did, we could match them up bijectively. Writing such a bijection in table form, we could form a new decimal x by running down the diagonal (taking the first digit from the first decimal, the second from the second, etc.) Changing EVERY digit of x (to something other than 9) produces a decimal that couldn't possibly have appeared on the original table (since it differs from each of those numbers in at least one digit).