Math. 55 EXAM. Model Solutions Prof. W. Kahan 2-3:30 pm. Thurs. 18 March 1999This 75 min. exam can be answered with the aid of any texts, notes and calculating instruments. Feel free to experiment; answers may be worked out as audaciously as you like on scratch paper but must then be reconsidered before being entered on this sheet in the spaces provided. Each correct proof, if required, earns two points; each almost complete proof or other correct answer earns a point; each incorrect answer loses a point; space left blank loses nothing, so DON’T JUST GUESS. The last problems are the hardest. Take your time; check your work. Finally hand just this sheet to your T. A. to be scored. Your score will affect your final grade. 1. Suppose positive integers M and N have GCD(M, N) = n·M – m·N = d for some unknown positive integers d, m and n . What is GCD(m, n) ? __ 1 __ [1 pt.]… because n·(M/d) – m·(N/d) = 1 See text p. 137 and p. 201 #58(b). 2. Given the prime p > 2 exhibit all pairs (x, y) of positive integers satisfying x 2 – y 2 = p .__ Only (x, y) = ( (p+1)/2 , (p–1)/2 ) because x–y = 1 and x+y = p . _______ [1 pt.]. See Fermat’s factorization algorithm in the solutions for the exam on 3 Mar. 3. Q(x) := ( (x–1) 3 + x 3 + (x+1) 3 )/ 3 . Prove that Q(k) ≡ 0 mod 3 for every integer k .___ Q(0) = 0 and Q(k ± 1)–Q(k) = ± 3(k 2 ± k + 1) ≡ 0 mod 3 ; now use induction. OrQ(k) = k 3 + 2k ≡ k + 2k ≡ 0 mod 3 by Fermat’s Little Theorem k p ≡ k mod p .Or Q(k) = k·(k 2 +2) ≡ k·(k 2 –1) ≡ (k+1)·k·(k–1) ≡ 0 mod 3 . ________ [2 pts.] See text p. 228 #18. 4. For which integers K > 0 is K 2 ≥ K ! ? _______ K = 1 , 2 and 3 . ________ [1 pt.]Prove your claim:___ Evidently 4 2 < 4 ! and 5 2 < 5 ! ; let’s use induction to prove K 2 < K ! if K ≥ 4 :Whenever K ≥ 4 and K ! > K 2 then (K+1) ! > (K+1) 2 too because(K+1) ! = (K+1)·K ! ≥ (K+1)·(K 2 + 1) > (K+1)·(K+1) = (K+1) 2 . _____ [2 pts.] See text p. 200 #28. 5. Alan and Bob prove short formulas for P n := (1 – 1/2)(1 – 1/3)(1 – 1/4) (…)(1 – 1/n) by induction: Alan’s Bob’s Asserted Formula: P n = 0 if integer n > 0. P n = 1/(2n) if integer n > 0 .Basis step: P 1 = 1 – 1/1 = 0 asserted. P 1 = 1 – 1/2 = 1/2 asserted.Inductive step: P n+1 = P n ·(1 – 1/(n+1)) P n+1 = P n ·(1 – 1/(n+1)) = 0·(n/(n+1)) = (1/(2n))·(n/(n+1)) = 0 corroborated. = 1/(2n+2) corroborated.What is the correct formula for P n ? _____ P n = 1/n _____ [1 pt.]… because the empty product P 1 = 1 , not 0 nor 1/2 . See text p. 228 #31.This document was created with FrameMaker404Math. 55 EXAM. Model Solutions Prof. W. Kahan 2-3:30 pm. Thurs. 18 March 1999 6. 0.110110001 is an example of a binary fraction. A set is well-ordered just when each of its nonempty subsets has a least element. Set B consists of all nonnegative binary fractions none of which has infinitely many 1 ’s to the right of the point. With the usual ordering for rational numbers, is B well-ordered ? (YES or NO) ___ NO ___ [1 pt.]… Insert more zeros between the point and subsequent bits of an alleged least elementof subset B – {0} to deduce that it cannot have a least element. See text p. 229 #36(c) 7. If and only if “Yes” or “No” would answer a question truly do Knights and Knaves answer it. Knaves always lie; Knights never lie; otherwise nobody else can tell them apart, as everyone knows. Two such Kn-persons entered a taxicab containing no one else but the driver, who asked one of them “Is either of you a Knight?” From his response the driver deduced correctly the answer to her question. Which of Knight or Knave was the Kn-person whom she had asked her question? __ KNAVE __ What kind was the other? __ KNIGHT __ [2 pts.] You actually do have enough information to solve this problem, which was made up by Raymond Smullyan. — The Knave’s response was “No”, a lie. Had the response been “Yes” the driver could not have decided between a Knight responding truthfully and one of two Knaves responding with a lie. See text p. 14 #41-42 and p. 177 “proof by cases.” The Kn-person’s practices are not entirely artificial. Some Easter Islanders really were like that; see renowned archaeologist Thor Heyerdahl’s book Easter Island, the Mystery Solved (1989, Random House). 8. A parking meter that accepts only 15¢ tokens and 20¢ tokens can hold at least 10000¢ worth of them. What lesser amounts can it hold? _ 0¢, 15, 20, 30, 35, 40, 45, 50, 55, …_[1 pt.]Prove your claim: All nonnegative multiples of 5¢ except 5¢, 10¢ and 25¢ can be held,as will now be proved by induction: The excepted sums are obvious, as are the first fewincluded sums; e.g. , 30¢ = 2·15¢ , 35¢ = 15¢ + 20¢ , 40¢ = 2·20¢ , 45¢ = 3·15¢ .Suppose now that 5n¢ is an included sum for n = 6, 7, 8, …, N , and that N ≥ 8 .Then 5(N+1)¢ = 5(N–2)¢ + 15¢ is an included sum too because N–2 ≥ 6 . __ [2 pts.] See text pp. 198-9 and p. 200 #31-3. 9. ƒ(0) = 1 , ƒ(1) = 0 , and ƒ((x+y)/2) = (ƒ(x) + ƒ(y))/2 for all integers x and y . Do these equations determine ƒ(k) uniquely at every integer k ? (YES or NO) __ YES __ [1 pt.]Set x = n+1 and y = n–1 to find ƒ(n+1) = 2ƒ(n)–ƒ(n–1) for n = 1, 2, 3, … in turn,and ƒ(n–1) = 2ƒ(n)–ƒ(n+1) for n = 0, –1, –2, –3, … in turn; so ƒ(k) = 1–k . 10. Let [x, y] and [[x, y], z] = [x, [y, z]] = [x, y, z] stand for ordered pairs and ordered triples whose atoms are selected by the notations [x, y] 1 := [x, y, z] 1 := x , [x, y, z] 3 := z , and [x, y] 2 := [x, y, z] 2 := y for all x, y and z . Suppose you are given a function £ that maps every ordered pair of positive integers to a positive integer, and a function P that maps every positive integer to an ordered pair of positive integers and satisfies P(£([m, n])) = [m, n] and £(P(k)) = k for all positive integers k,