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.
[Show More]
