All 5 questions on Midterm 2 were worth 20 points. Question 1 ---------- Among a group of 3 cats (Tabby, Leo, and Garfield) and 4 dogs (Snoopy, Odie, Fido, and Bowser) we wish to arrange a photograph of 5 of them. How many ways are there to arrange 5 of the animals in a photograph under the following conditions (each set of conditions is independent of the others): 1) No conditions; any 5 animals may appear in any order. 2) There must be exactly 3 dogs in the photograph. 3) A cat must be in either the leftmost position or the rightmost position. Hint: Use inclusion-exclusion. Answer to Question 1: --------------------- (1) Worth 7 points. There are 7 choices for the leftmost position, 6 remaining choices for the next position, 5 for the next, 4 for the next, and 3 for the rightmost position. By the product rule, we have P(7,5) = 7*6*5*4*3 = 2520 arrangements. Little partial credit was given for errors here. Three points were awarded for calculating C(7,5) instead of P(7,5). (2) Worth 6 points. There are C(4,3) = C(4,1) = 4 ways to choose 3 dogs for the picture. Then there are 5*4*3 ways to choose positions for them in the picture. Then we have to choose 2 cats for the other 2 spots in the picture. There are C(3,2) = 3 ways to do this, and then 2 ways to arrange the cats in the 2 vacant spots left in the picture. Multiplying all of these choices together, we get 4*(5*4*3)*3*2 = 1440. Partial credit was given only in very special cases, because there is little work to show other than writing down the factors in the multiplication. (3) Worth 7 points. We use inclusion-exclusion. Let S be the set of all arrangements with a cat in the leftmost position, and let T be the set of all arrangements with a cat in the rightmost position. We want to find |S U T|. By inclusion-exclusion, |S U T| = |S| + |T| - |S intersect T|. Now we find |S|. There are 3 choices for a cat in the leftmost position. The remaining spots of the photo can be filled out without restriction. So there are 6*5*4*3 ways do accomplish this. Hence, |S| = 3*6*5*4*3 = 1080. By symmetry, |T| = 1080. Finally, we must calculate |S intersect T|, the number of arrangements with cats in the left and right-most positions. There are 3 ways to choose a cat for the leftmost position. Then 2 choices remain for a cat in the rightmost position. The middle 3 spots can then be filled out without restriction in 5*4*3 ways. So we get a total of |S intersect T| = 3*2*5*4*3 = 360. Hence, |S U T| = 1080 + 1080 - 360 = 1800. About 4-5 points were awarded for correctly calculating |S|, but forgetting (or messing up) the subtraction of the intersection. Question 2 ---------- What is the least positive integer n such that n mod 5 = 3 and n mod 7 = 4? Answer to Question 2: --------------------- By the Chinese Remainder Theorem, we know that this system has a solution in the range 1 to 35, and that all solutions are congruent mod 35. We also know there is a solution of the form 3*7*x + 4*5*y, where x is the inverse of 7 modulo 5 and y is the inverse of 5 modulo 7. We can take x=y=3. Then 3*7*3 + 4*5*3 = 123 is a solution. When we reduce 123 mod 35 we get 18. This is the least positive solution. If the student said that 18 was the answer, he got the full twenty points. If not, the student got five points for each of the following: 1) correctly setting up the problem with the right numbers in the right places; 2) correctly determining the first of the two inverses needed to solve the problem they set up; 3) correctly determining the second of the two inverses needed to solve the problem they set up; and, 4) reducing the calculated value modulo the product of the divisors for the problem they set up. At least one student did the correct calculation and then asserted that there was no solution; that student got 15 points. Question 3 ---------- Consider the sequence defined by: A(0) = 1, A(1) = 0, and A(n) = 4A(n-2) - 3A(n-1) for n >= 2. 1) List the first six terms in the sequence. 2) Find a closed formula for the sequence. That is, find a formula for A(n) which does not refer to A(k) for any k<n. Hint: begin by considering solutions of the form A(n) = r^n for some constant r, and solve for r. Answer to Question 3: --------------------- 1) The first six terms in the sequence, starting with A(0), are: 1, 0, 4, -12, 52, -204. (This was worth six points. One point was deducted for each wrong answer, with a maximum of two points off for any particular arithmetic error. So for instance if a wrong answer to A(2) threw off A(3) through A(6), which would have otherwise been right, two points were deducted.) 2) If there were a solution of the form r^n, then because of the recurrence relation, we would have r^n = 4r^(n-2) - 3r^(n-1). Solving for r, we get r^(n-2)*(r^2 +3r -4) = 0, and the quadratic polynomial has roots 1 and -4. So 1^n and (-4)^n both satisfy the recurrence relation A(n) = 4A(n-2) - 3A(n-1), as does any linear combination of 1^n and 4^n, but they don't yet satisfy the two initial conditions A(0)=1, A(1)=0. So we want to find constants a and b such that a*1^n + b*(-4)^n satisfy the initial conditions. Plugging in n=0 and setting A(0) = a*1^0 + b*(-4)^0 equal to 1 gives a+b=1. Similarly, the initial condition A(1)=0 yields a-4b = 0. Solving these 2 equations for a and b, we get a = 4/5 and b = 1/5. So the answer is A(n) = (4/5) + (1/5)*(-4)^n. (This was worth 14 points. 7 points were given for finding the roots of the proper polynomial, and the remaining 7 points were given for finding a and b and putting it all together. Many people who didn't get very far received one point for recognizing that the sequence was alternating after n=1, and suggesting that therefore (-1)^n was involved in the answer (even though it wasn't).) Question 4 ---------- Prove by induction that 10^n + 3*4^(n+2) + 5 is divisible by 9 for all nonnegative integers n. Answer to Question 4 -------------------- The base case is n=0 (0 is first among all nonnegative integers, although no points were deducted for those who started with n=1). Here we simply compute 10^0 + 3*4^2 + 5 = 54 = 6*9, which is divisible by 9. The induction step is to assume that B(n) = 10^n + 3*4^(n+2) + 5 is divisible by 9, and to show that B(n+1) = 10^(n+1) + 3*4^(n+3) + 5 is divisible by 9. (Students getting this far in the answer were given 5 points). Now we compute B(n+1) = 10^(n+1) + 3*4^(n+3) + 5 = 10*10^n + 3*4*4^(n+2) + 5 = 9*10^n + 10^n + 3*3*4^(n+2) + 3*1*4^(n+2) + 5 = 9*10^n + 9*4^(n+2) + B(n) Since each of the three terms in the last sum is divisible by 9 (the first two by "inspection", the last by induction), their sum, B(n+1), is divisible by 9 as desired. 15 more points were awarded for doing this computation (or one like it) correctly, and drawing the correct conclusion. Question 5 ---------- Each part of this problem contains a statement and a "proof" of that statement. For each part, you must (a) say whether the statement is true or false (and if it is false, provide a counterexample) (b) say whether the proof is valid or invalid (and if it is invalid, describe where and how it goes wrong). (1) Statement: ``For any positive integer n, if 45|n^2, then 45|n.'' (Recall that a|b means ``a divides b''). Here is the proof (with line numbers added for convenience): (1) 45|n^2 -> (3|n^2 and 5|n^2), since 45 is a multiple of both 3 and 5. (2) 3|n^2 -> 9|n^2, since the exponent of every prime in the prime factorization of n^2 must be even. (3) Now, 45|n -> (9|n and 5|n), since 45 is a multiple of both 5 and 9. Hence 9|n^2 and 5|n^2, as required. So 45|n. (2) Statement: ``If p is a prime and greater than 3, then p^2 is congruent to 1 mod 24.'' Here is the proof (with line numbers added for convenience). The notation "a \= b" means "a is not equal to b". (1) p is a positive prime equal to neither 2 nor 3. (2) Since p is not equal to 2, then p is not congruent to 0 mod 6, 2 mod 6, or 4 mod 6, for otherwise p would be divisible by 2. (3) Since p is not equal to 3, then p is not congruent to 0 mod 6 or 3 mod 6, for otherwise p would be divisible by 3. (4) Thus p is congruent to 1 mod 6 or 5 mod 6. (5) Hence p^2 is congruent to 1 mod 6 or 25 mod 6. (6) But 25 is congruent to 1 mod 6, so p^2 is congruent to 1 mod 6. (7) Since p is not equal to 2, then p is not congruent to 0 mod 4 or 2 mod 4, for otherwise p would be divisible by 2. (8) Thus p is congruent to 1 mod 4 or 3 mod 4. (9) Hence p^2 is congruent to 1 mod 4 or 9 mod 4. (10) But 9 is congruent to 1 mod 4, so p^2 is congruent to 1 mod 4. (11) We now apply the Chinese Remainder Theorem: Since p^2 is congruent to 1 mod 6 and p^2 is congruent to 1 mod 4, we conclude that p^2 is congruent to 1 mod (6 * 4). (12) But (6 * 4) = 24, so we conclude that p^2 is congruent to 1 mod 24. Answer to Question 5 -------------------- Part (1): a) Statement is false (Counterexample: any n that is a multiple of 15 but NOT a multiple of 45). b) Proof is invalid, of course (line 3 is a classic example of begging the question). Grading criteria: a) Saying it's true: 0 points Saying it's false without giving a counterexample (or providing an incorrect one): 1 point Saying it's false and providing a counterexample: 3 points b) Saying proof is valid: 0 points Saying it's invalid but not giving a reason why: 1 point Saying it's invalid but giving a bogus reason why: 1-6 points, depending on bogosity. Usually 1 point. Saying it's invalid, because line 3 begged the question/used circular reasoning/assumed what we wanted to prove/equivalents: 7 points Part (2): a). Statement is true (see Note below). b). Proof is invalid (on line 11, we cannot apply the Chinese remainder Theorem, since 6 and 4 are not relatively prime). (Note: while you're not required to prove the statement, it is not difficult to do so; for example, the above proof goes through if, instead of using 6 and 4, we use 8 and 3. Other simple proofs are possible.) Grading criteria: a) Saying it's false: 0 points Saying it's true: 3 points b) Saying proof is valid: 0 points Saying proof is invalid, but not saying why: 1 point Saying proof is invalid, but giving a bogus reason why: 1-6 points, depending on bogosity. Note especially that merely mentioning the Chinese Remainder Theorem won't get you full credit here. Saying proof is invalid, with the reason being: the use of the CRT on line 11 is not allowed, since 6 and 4 are not relatively prime: 7 points.