MACM 101 Quiz 2

MACM 101 Quiz 2 (in the class) November 15, 2019. Total Marks: 40 1. (10 points) (a) Determine the size of the sample space of the following experiment. i. Tossing a coin two times. Ans: The order is implicitly inv ...

MACM 101 Quiz 2 (in the class) November 15, 2019. Total Marks: 40 1. (10 points) (a) Determine the size of the sample space of the following experiment. i. Tossing a coin two times. Ans: The order is implicitly involved. The sample space is f(H;H); (H;T);(T;H);(T;T)g. If the order is not implied, the sample space is ffH;Hg;fH;Tg;fT;Tgg. In this case, the probability of each sample point is not the same. If any student replies with order not implied, the non-uniformity of the probabilities should be mentioned. If it is missing, deduct 1 point. 2 points are assigned for this question. ii. Rolling two distinct dice. Ans: The order is implicitly involved. The sample space is f(i; j);1 ≤ i ≤ 6;1 ≤ j ≤ 6g. If the order is not implied, the sample space is ffi; jg;1 ≤ i ≤ 6;i ≤ j ≤ 6g. In this case, the probability of each sample point is not the same. If any student answers with order not implied, the non-uniformity of the probabilities should be mentioned. If it is missing, deduct 1 point. 2 points are assigned for this question. (b) The universal set U has N elements, including the letter A. Show that the fraction of all subsets of size r that contain A is r N . Ans: Let XA be the set of all subsets of size r that contains the element A. We know that jXAj = C(N −1;r −1). The number of r-size subsets one can obtain is C(N;r). Therefore, the fraction of all subsets of size r that contain A is C(N−1)(r−1) C(N;r) . The fraction is (N−1)! (r−1)!×(N−r)! × r!×(N−r)! N! = r=N. 6 marks are assigned for this part. Students should clearly write the two expressions. Deduct 1 mark for missing each expression. They must provide the simplification steps to show the answer to be Nr . Deduct 1 mark if it is missing. 2. (10 points)(a) Use the prime factorization method to find gcd(124,96). Ans: Prime factorization of 124 = 22 ×311. Prime factorization of 96 = 25 ×31. Therefore, gcd(124;96) = 2min(2;5) ×3min(0;1) ×31min(1;0) = 22 = 4. 3 points The definition of gcd using prime factorization (i.e. the last line) must be specified. Deduct one mark if the definition is missing. (b) Use the Euclidean algorithm to find gcd(124,96). Show every step. Ans: We can write 124 = 1×96+28 (1) 96 = 3×28+12 (2) 28 = 2×12+4 (3) 12 = 3×4+0 (4) 3 points are assigned for this part. Deduct marks if some steps are missing. (c) Find integers u and v such that gcd(124;96) = 124u+96v. Show every step. Ans: We can write 4 = 28−2×12 from (3) = 28−2×(96−3×28) from (2) = 7×28−2×96 = 7×(124−1×96)−2×96 from(1) = 7×124+ (−9)×96 We set u = 7 and v = −9. 4 points are assigned for this part. Deduct marks if some steps are missing. 3. (10 points) (a) What is the main difference between regular mathematical induction and strong mathematical induction? Ans: Suppose we want to prove 8 n ≥ n0(2 N) S(n) is true where S(n) is an open statement. In regular induction we want to show that S(n0)^S(k) ! S(k +1) for any arbitrary k ≥ n0. In strong induction we want to show that S(n0)^S(n0 +1)^:::^S(k− 1)^S(k) ! S(k +1) for any arbitrary k ≥ n0. 4 points for this part. The definition should be complete. If it is not (only basis is mentioned but not the inductive hypothesis; only inductive hypothesis but not the basis), deduct two marks.(b) You are asked to solve the following problem using the Principle of Strong Induction. For any integer n ≥ 35 there exist nonnegative integers x and y such that n = 5x+9y. Ans: We want to show that 8 n ≥ 35 S(n) is true where the open statement S(n) : n can be written as n = 5x+9y where x and y are nonnegative integers. We will use strong induction. Basis Show that S(35) ^ S(36) ^ S(37) ^ S(38) ^ S(39) is true. This can be easily shown to be true. Inductive hypothesis Suppose S(35) ^ S(36) ^ ::: ^ S(k) is true for arbitrary k ≥ 39. Show that S(k +1) is also true. Let m = k+1−5. Since k ≥ 39, m ≥ 35. Since m ≥ 35 and less than k, by the induction hypothesis,S(m) is true. We can, therefore, write m = 5×u+9×v where u and v are nonnegative integers. Therefore, k+1 = m+5 = 5×(u+1)+ 9×v. Thus S(k +1) is true. By the principle of strong induction we claim that 8 n ≥ 35 S(n) is true. There should be a clear statement indicating the three steps for the induction proof. If they are missing, deduct 1 mark. It must be mentioned that it is a strong induction. If it is missing, deduct .5 marks. All the elements of the basis should be shown to be correct. If it is not complete, deduct 1 mark. The third step should be clear. If there is any vagueness, deduct marks appropriately. 4. (10 points) (a) Let f : Z+ ! Z+ where for all x 2 Z+; f(x) = x+1. What is the range of f? Is f one-to-one? Is it onto? Justify. Ans: The range of f is f2;3;4;:::g. f is one-to-one, but not onto. They must provide proofs to show that f is one to one and f is onto. 6 marks are allotted for this question. The proofs should be complete. If it is not complete, deduct 1-2 points. (b) Let f : R ! R;g : R ! R be defined by f(x) = x2;g(x) = x+5. Determine (g◦ f)(x) and (f ◦g)(x). Ans: It is an easy question. (g◦ f)(x) = x2+5 and (f ◦g)(x) = (x+5)2. 4 points are allotted. Marks should be deducted for incomplete answers.