Solution for 2021-2022 COMP2711H Midterm examination PDF

Preview

Summary

This is the solution for the midterm examination of COMP2711H in the academic year 2021-2022....

Description

COMP 2711H Discrete Mathematical Tools for Computer Science Solutions to Mid-term Exam Problem 1 (a) False. Let the domain of x be {x1 , x2 } and the domain of y be {y1 , y2 }. Let P (x, y ) be a propositional function that has the following truth value. y1 y2

x1 x2 T F F T

In this setting, ∀y∃xP (x, y) is true, but ∃x∀yP (x, y ) is false. (b) True. If ∃x∀yP (x, y) is true, then there is some x, namely x0 , such that for all y , P (x0 , y) is true. Therefore, for all y, x0 makes P (x0 , y) true, which implies that ∀y ∃xP (x, y) is true. Problem 2. Suppose for the sake of contradiction that r is rational. We can write r = ba where a and b are two relatively prime integers. Then we have that a5 a3 + 3 + 1 = 0, b b5 or, equivalently,

a 5 + a 3 b2 + b5 = 0

( ∗)

Next we will show that no relatively prime integers a and b will make equation (∗) hold, which leads to a contradiction. There are three cases to consider (since a and b cannot both be even): (i) a is odd, and b is odd. Then we have that a5 , a3 b2 , and b5 are all odd. As a result a5 + a3 b2 + b5 is also odd and cannot be 0. (ii) a is odd, and b is even. Then we have that a5 is odd, a3 b2 is even, and b5 is even. Again, a5 + a3 b2 + b5 is odd and cannot be 0. (iii) a is even, and b is odd. Then we have that a5 is even, a3 b2 is even, and b5 is odd. So, a5 + a3 b2 + b5 is odd and cannot be 0. As we get a contradiction in each case, it follows that our assumption that r is rational is false. Thus we have proved that r is rational. Problem 3. (a) (A nand B) nand (A nand B ) ≡¬((A nand B) ∧ (A nand B)) ≡¬(A nand B) ≡¬(¬(A ∧ B))

(by definition) (Idempotent laws) (by definition)

≡A ∧ B

(Double negation laws) 1

(b) A nand A. Justification of equivalence: A nand A ≡¬(A ∧ A)

(by definition)

≡¬A

(Idempotent laws)

(c) (A nand A) nand (B nand B). Justification of equivalence: (A nand A) nand (B nand B ) ≡¬A nand ¬B (by part (b)) ≡¬(¬A ∧ ¬B) ≡¬(¬A) ∨ ¬(¬B)

(by definition) (De Morgan’s laws)

≡A ∨ B

(Double negation laws)

Problem 4. Let a and b be two positive integers. We wish to find their greatest common devisor GCD(a, b). At each step of Euclid’s algorithm, we transform the two arguments of the GCD into two smaller numbers, until the second argument (a mod b) evaluates to 0. We are then left with GCD(b, 0), which returns b. Each step is carried out using the identity: GCD (a, b) ≡ GCD (b, a mod b) Since this identity is the only identity that is recursively used in the algorithm, it suffices to prove this identity in order to prove the algorithm’s correctness. It can be proven by showing the following two inequalities are true. We will make use of the fact that if an integer divides two integers a and b, then it also divides any integer linear combination of a and b. Also, we will make use of the fact that a mod b can be written as a − qb, where q ∈ Z . First, we prove that GCD(b, a mod b) ≥ GCD(a, b). Let c = GCD(a, b). By definition of GCD, we know that the c divides a and b. It follows that c divides b and a mod b (which equals a − qb). Thus GCD(b, a mod b) ≥ c = GCD(a, b). Next we prove that GCD(a, b) ≥ GCD(b, a mod b). Let d = GCD(b, a mod b). Note that a = (a mod b) + qb. It follows that d divides a and b. Thus GCD(a, b) ≥ d = GCD(b, a mod b). Combining the above two inequalities, we obtain GCD(a, b) = GCD(b, a mod b), which proves that the identity utilised by the algorithm is correct, implying the correctness of the algorithm. 2

Problem 5. Note that pq−1 + q p−1 ≡ 1 (mod pq) is equivalent to pq|(pq−1 + q p−1 − 1). To prove this, we will show that both p and q divide pq−1 + q p−1 − 1. Since p and q are distinct prime numbers, p ∤ q. By Fermat’s Little Theorem, we have q p−1 ≡ 1 (mod p). Equivalently p|q p−1 − 1. Obviously we also have p|pq−1 . Adding, we obtain p|pq−1 + q p−1 − 1. Similarly, we can show that q|pq−1 + q p−1 − 1. Since both p and q divide pq−1 + q p−1 − 1, and p and q are relatively prime, it follows that pq|pq−1 + q p−1 − 1. Equivalently pq−1 + q p−1 ≡ 1 (mod pq), as desired. [Alter.] Since p and q are distinct prime numbers, p is not divisible by q and q is not divisible by p. From Fermat’s Little Theorem, we have: pq−1 ≡ 1 (mod q) q p−1 ≡ 1 (mod p) Equivalently, pq−1 − 1 ≡ 0 (mod q) and q p−1 − 1 ≡ 0 (mod p). It follows that (pq−1 − 1)(q p−1 − 1) ≡ pq−1 q p−1 − (pq−1 + q p−1 − 1) ≡ 0 (mod pq). As p ≥ 2 and q ≥ 2 (minimal prime number is 2), q − 1 ≥ 1 and p − 1 ≥ 1. So pq | pq−1 q p−1 . It follows that pq−1 + q p−1 ≡ 1 (mod pq), which ends the proof. Problem 6. (a) We have 4 choices of a box for each ball, so by the product rule, the number of ways is 412 . (b) Imagine placing the 12 balls in a row. We have to assign a “box label” to each ball, such that exactly 3 balls are assigned the labels 1 to 4. This is the same as the number of arrangements of 12 objects, where the objects are of 4 different types and there are exactly 3 objects of each type. The total number of ways is therefore (312!)!4 . (c) The difference between parts (b) and (c) is that the boxes are distinct in (b) but identical in (c). Note that each arrangement of (c) corresponds to 4 ! different arrangements in (b). Thus the number of ways, treating boxes as ! . identical, is (3 12 !)4 ·4 ! (d) Imagine placing the 12 balls in a row, where each ball is represented by a star. As all the balls are identical, we only need to decide the number of balls to place in each box. We can do this by placing 3 bars to partition the 12 stars into 4 groups. The number of ways in which we can do this is the same as the number of arrangements of 15 objects, 12 of which are of one type (stars) and 3 are of another type (bars). This is the same as the number of ways of choosing 3 positions out of 15 in which to place the bars, which is 15 . 3 (e) First we place one ball in each box since each box is required to contain at least one ball. The number of ways in which we can distribute the remaining 8 balls among 4 boxes can exactly as in part (d). Hence the    be determined number of ways is 8+43−1 = 11 . 3 3

Problem 7. (a) For any valid pair (A, B), each element of S belongs to one of the following sets: A, B − A, S − B. Therefore, the problem is equivalent to distributing n distinct elements into 3 distinct sets. Thus, there are 3 choices for each of the n elements. Hence the number of pairs is 3n . (b) The identity is n   X n k 2 . 3 = k k=0 n

The LHS is the number we get in (a). We give a combinatorial proof of the identity by counting the number of (A, B) pairs in a different way. Suppose that we first choose the subset B and then choose any subset nA of B . The number of ways in which we can choose a subset B of size k is k . For a k fixed set B having k elements, we can construct A from B  in 2 ways. Thus n k the total number of (A, B) pairs possible for fixed k is k 2 . Summing over all possible values of k gives the expression on the right hand side. (c) Applying the binomial theorem, we have: 3n =(1 + 2)n n   X n n−k k 1 2 = k k=0 n   X n k 2 . = k k=0

4...