Queen’s University School of Computing
CISC 203: Discrete Mathematics for Computing II
Problem Set 1 Solutions
Due September 24, 2021 by 11:59pm (Kingston time)
Show all your work/steps and explain all your solutions.
Problem set collaboration policy:
1. This problem set is an individual assessment that is meant to replace an in-class test, i.e., you are
expected to solve the problems and write your solutions individually. However, it is open book and
you are being given an extended period of time to help better manage your learning workload.
2. Do not ask the TAs or other students for help on directly solving the problem set questions. However,
you may identify examples or exercises in the course notes that refer to similar concepts or require
a similar strategy to solve (identifying such connections between questions demonstrates individual
effort in solving the problem), and may ask for help during office hours or on the discussion board to
understand those examples.
3. Do not publicly post (e.g., on the discussion board or Microsoft Teams) that “Question X in the
problem set is similar to Question Y in the course notes”. It is important that each student becomes
familiarized enough with the material to observe such connections on their own.
4. If you encounter any explanations on the discussion board or during office hours that help you to
solve a question, add a sentence to your solution(s) (and provide the URL if applicable) to give credit.
Failure to do so may result in penalty (when in doubt, no need to ask—just give credit).
5. Questions about clarifying any aspect of the problem set (e.g., to clarify the wording of a question)
should be posted on the discussion board topic, so that all students can benefit equally from the answer:
https://discourse.caslab.queensu.ca/c/cisc-203-f21/33.
Your solutions must be prepared in LATEX using the Overleaf template, as follows:
I. Log in using your NetID, by clicking the “Log in through your institution” button at the bottom of
this page: https://www.overleaf.com/edu/queensu
II. Access the template here: https://www.overleaf.com/read/ncdhzmmxtkzj
III. Click “Menu” on the top left corner and then on “Copy Project” to create your copy of the template.
IV. When you are finished writing your solutions, download your PDF and submit it on onQ.
Note: 2 marks (out of 68) in Problem Set 1 are reserved for formatting, which consists of correctly
entering your name into the LATEX template, removing the sample text/images from it, and formatting your
solutions in a way that is readable by the TAs (please be considerate of them), e.g., by inserting line breaks
where appropriate. Everybody should be able to get these 2 marks!
1.[14 marks] (a) Prove (A ∪B)C = AC ∩BC using Proof Template 5.
(b) For A = {a ∈ R : |a| ≤ 2} and B = {b ∈ R : |b| = 2}, write A×B and B×A in set-builder notation
and plot the elements of (A×B) ∪ (B ×A) on an xy-plane.
(c) Let n ∈ N and n > 0, and let the set An = {x ∈ R : − 1n ≤ x ≤
1
n
}.
Find (i)
⋃∞
n=1 An and (ii)
⋂∞
n=1 An and prove your answers using an appropriate proof technique.
https://discourse.caslab.queensu.ca/c/cisc-203-f21/33
https://www.overleaf.com/edu/queensu
https://www.overleaf.com/read/ncdhzmmxtkzj
CISC 203: Discrete Mathematics for Computing II
Problem Set 1 Solutions, Fall 2021 Page 2
Solution:
(a) (4 marks)
We use Proof Template 5 as follows.
Step 1 (2 marks):
Let x ∈ (A ∪B)C. This implies:
x 6∈ A ∪B
⇒ x 6∈ A and x 6∈ B
⇒ x ∈ AC and x ∈ BC
⇒ x ∈ AC ∩BC
So, x ∈ (A ∪B)C ⇒ x ∈ AC ∩BC.
Step 2 (2 marks):
Now, let x ∈ AC ∩BC. This implies:
x ∈ AC and x ∈ BC
⇒ x 6∈ A and x 6∈ B
⇒ x 6∈ A ∪B
⇒ x ∈ (A ∪B)C
So, x ∈ AC ∩BC ⇒ x ∈ (A ∪B)C.
• 2 marks for first half: x ∈ (A ∪B)C ⇒ x ∈ AC ∩BC
• 2 marks for second half: x ∈ AC ∩BC ⇒ x ∈ (A ∪B)C
(b) (4 marks)
A is the set of a real numbers between −2 and 2, inclusive, i.e., it is the set of all real numbers in the
closed interval [−2, 2]. B is the set {−2, 2}.
So, A × B = {(a, b) ∈ R2 : |a| ≤ 2 and |b| = 2} and B × A = {(b, a) ∈ R2 : |a| ≤ 2 and |b| = 2}. (1
mark each)
The points in A×B and B ×A are plotted below in red and blue, respectively. (2 marks)
−4 −2 0 2 4
−4
−2
0
2
4
x
y
A×B
B ×A
(c) (6 marks)
(i)
⋃∞
n=1 An = {x ∈ R : −1 ≤ x ≤ 1} = [−1, 1]. (1 mark)
CISC 203: Discrete Mathematics for Computing II
Problem Set 1 Solutions, Fall 2021 Page 3
We prove this using Proof Template 5:
Step 1 (1 mark):
Let x ∈
⋃∞
n=1 An. This implies x ∈ An for at least one n ∈ N
+.
So, x ∈ [− 1
no
, 1
no
] for at least one no ∈ N+.
Since no ≥ 1, we have [−1no ,
1
no
] ⊆ [−1, 1]. So, x ∈ [−1, 1].
We have thus shown that x ∈
⋃∞
n=1 An implies x ∈ [−1, 1].
Step 2 (1 mark):
Let x ∈ [−1, 1]. Then, x ∈ A1 = [−1, 1], so x ∈
⋃∞
n=1 An.
We have thus shown that x ∈ [−1, 1] implies x ∈
⋃∞
n=1 An.
(ii)
⋂∞
n=1 An = {0}. (1 mark)
Proof (2 marks):
Let x ∈
⋂∞
n=1 An, which means that x ∈ An for all n ∈ N
+. So, −1
n
≤ x ≤ 1
n
for all n ∈ N+.
If x > 0, then, there exists an no ∈ N+ such that x 6≤ 1no . So, if x > 0, then x 6∈
⋂∞
n=1 An.
If x < 0, then, there exists an no ∈ N+ such that −1n 6≤ x. So, if x < 0, then x 6∈ ⋂∞ n=1 An. If x = 0, then, −1 n ≤ x ≤ 1 n for all n ∈ N+ and thus x ∈ An for all n ∈ N+. So, if x = 0, then x ∈ ⋂∞ n=1 An. So, ⋂∞ n=1 An = {0}. 2.[14 marks] Let R be the relation defined on the set Z by a R b if 3 | (a2 − b2). Prove that R is an equivalence relation and provide all the distinct equivalence classes. Hint: You may use the property that 3 | mn implies that 3 must divide either m or n or both. Solution: Suppose that a, b, c ∈ Z. (2 marks: reflexivity) First, we show that R is reflexive. Since a | (a2 − a2) (i.e., a divides 0), then a R a. (2 marks: symmetry) Next, we show that R is symmetric. Suppose that a R b and thus 3 | (a2− b2). So, by the definition of the divides-by relation we have a2 − b2 = 3k for some k ∈ Z. Multiplying both sides of the equation by −1 gives us b2 − a2 = −3k. So, b2 − a2 = 3l for l = −k. Therefore, 3 | (b2 − a2) which means that b R a. (2 marks: transitivity) Finally, we show that R is transitive. Suppose that a R b and b R c. This means that 3 | (a2 − b2) and 3 | (b2 − c2). So, a2 − b2 = 3k and b2 − c2 = 3l for k, l ∈ Z. We want to check if a R c, i.e., if 3 | (a2− c2). By substitution, we find a2− c2 = (b2 + 3k)− (b2− 3l) = 3k + 3l = 3(k + l). So, a2 − c2 is a multiple of 3, which means that 3 | (a2 − c2) and thus a R c. Since R is reflexive, symmetric, and transitive, it is an equivalence relation. Now, we must find the equivalence classes of R. (2 mark: breaking relation down into two cases) We know that a R b if and only if 3 | (a2 − b2). Since a2− b2 = (a− b)(a+ b), we can rewrite this divisibility relation as 3 | (a− b)(a+ b), which implies 3 | (a− b) or 3 | (a + b) (we deduce this from the property that 3 | mn implies that 3 must divide either m or n or both). So, we require that either a− b = 3k or a + b = 3k, for k ∈ Z. So, a R b requires that either a = 3k + b or a = 3k − b. (2 mark: equivalence class [0]) The equivalence class [0] consists of all the elements a ∈ Z such that a R 0, i.e., all the elements a ∈ Z such that a = 3k + 0 or a = 3k − 0 (or in other words, all multiples of 3): CISC 203: Discrete Mathematics for Computing II Problem Set 1 Solutions, Fall 2021 Page 4 [0] = {a ∈ Z : a = 3k + 0 or a = 3k − 0} = {a ∈ Z : a = 3k} = {. . . ,−9,−6,−3, 0, 3, 6, 9, . . .} (2 mark: equivalence class [1]) The equivalence class [1] consists of all the elements a ∈ Z such that a R 1, i.e., all the elements a ∈ Z such that a = 3k + 1 or a = 3k− 1 (or in other words, all integers that are not multiples of 3): [1] = {a ∈ Z : a = 3k + 1 or a = 3k − 1} = {. . . ,−8,−7,−5,−4,−2,−1, 0, 1, 2, 4, 5, 7, 8, . . .} (2 mark: justification that [0] and [1] are the only distinct equivalence classes) Since [0] is the set of all integers that are a multiple of 3 and [1] is the set of all integers that are not a multiple of 3, then we have [0] ∪ [1] = Z and thus [0] and [1] are the only two distinct equivalence classes of R. 3.[12 marks] (a) A group of 240 students were surveyed to see what computer games they play, and the following results were obtained: • 92 students play DOTA2 • 104 students play CS:GO • 100 students play TF2 • 50 students play both DOTA2 and CS:GO • 42 students play both DOTA2 and TF2 • 46 students play both CS:GO and TF2 • 32 students play DOTA2, CS:GO, and TF2 How many students play: i At least one of the games? ii Only one of the games? iii None of the games? iv Only DOTA2, but not CS:GO or TF2? v DOTA2 and CS:GO, but not TF2? Show your work using set operations. Solution: 5 marks: For each part, a 0.5 mark is assigned for stating the correct numeric result (no quarter-marks provided), and a 0.5 mark for stating the correct set operations (also no quarter-marks provided). Let U be the set of all students surveyed, D be the set of students who play DOTA2, C be the set of students who play CS:GO, and T be the set of students who play TF2. i |D ∪C ∪ T | = |D|+ |C|+ |T | − |D ∩C| − |D ∩ T | − |C ∩ T |+ |D ∩C ∩ T | = 92 + 104 + 100− 50− 42− 46 + 32 = 190 students play at least one of the games. ii |D − C − T |+ |C −D − T |+ |T −D − C| = |D| − |D ∩C| − |D ∩ T |+ |D ∩C ∩ T |+ |C| − |C ∩D| − |C ∩ T |+ |C ∩D ∩ T |+ |T | − |C ∩ T | − |C ∩D|+ |C ∩D ∩ T | = 92− 50− 42 + 32 + 104− 50− 46 + 32 + 100− 42− 46 + 32 = 116 students play only one of the games. iii U − |D ∪ C ∪ T | = 240− 190 = 50 students play none of the games. CISC 203: Discrete Mathematics for Computing II Problem Set 1 Solutions, Fall 2021 Page 5 iv |D| − |D ∩ C| − |D ∩ T |+ |D ∩ C ∩ T | = 92− 50− 42 + 32 = 32 students play only DOTA2, but not CS:GO or TF2. v |D ∪ C| − |D ∩ C ∩ T | = 50− 32 = 18 students play DOTA2 and CS:GO, but not TF2. (b) Consider the set A = {1, 2, . . . , 9999}. Using the principle of inclusion-exclusion, determine: i The number of elements in A divisible by at least one of 2, 3, 5, and 7. ii The number of elements in A divisible by none of 2, 3, 5, and 7. Solution: (7 marks) Number of elements divisible by 2 = b 9999 2 c = 4999. Number of elements divisible by 3 = b 9999 3 c = 3333. Number of elements divisible by 5 = b 9999 5 c = 1999. Number of elements divisible by 7 = b 9999 7 c = 1428. Number of elements divisible by both 2 and 3 is the number of multiples of 6 = b 9999 6 c = 1666. Number of elements divisible by both 2 and 5 is the number of multiples of 10 = b 9999 10 c = 999. Number of elements divisible by both 2 and 7 is the number of multiples of 14 = b 9999 14 c = 714. Number of elements divisible by both 3 and 5 is the number of multiples of 15 = b 9999 15 c = 666. Number of elements divisible by both 3 and 7 is the number of multiples of 21 = b 9999 21 c = 476. Number of elements divisible by both 5 and 7 is the number of multiples of 35 = b 9999 35 c = 285. Number of elements divisible by 2, 3, and 5 is the number of multiples of 30 = b 9999 30 c = 333. Number of elements divisible by 2, 5, and 7 is the number of multiples of 30 = b 9999 70 c = 142. Number of elements divisible by 2, 3, and 7 is the number of multiples of 42 = b 9999 42 c = 238. Number of elements divisible by 3, 5, and 7 is the number of multiples of 105 = b 9999 105 c = 95. Number of elements divisible by 2, 3, 5, and 7 is the number of multiples of 210 = b 9999 210 c = 47. (i) Number of elements divisible by at least one of 2, 3, 5, and 7 = (4999 + 3333 + 1999 + 1428)− (1666 + 999 + 714 + 666 + 476 + 285) + (333 + 142 + 238 + 95)− 47 = 7714. (3 marks) (ii) Number of elements divisible by none of 2, 3, or 5 = 9999− 7857 = 2285. (2 marks) Marks: 2 marks total for showing how to obtain number of elements divisible by 2, 3, 5, 7, etc. 3 marks total for (i) 2 marks for showing work (adding cardinality of each set, subtracting car- dinalities of pairwise intersections, adding cardinalities of triplewise intersections, and subtracting cardinality of quadruple-wise intersection), 1 mark for the answer 2 marks total for (ii) 1 mark for showing work (9999 minus the union of the previous sets), 1 mark for answer 4.[14 marks] Give a combinatorial proof (an algebraic proof will not be accepted: see Module 1, Proposition 15 and Module 3, Theorem 3 for two examples of combinatorial proofs) that( 3n 3 ) = n3 + 3 · ( n 3 ) + 6 · ( n 1 )( n 2 ) . Solution: (2 marks: stating the question) Suppose that we are trying to count the number of ways to form a team of 3 students picked from 3 different departments with n students each. (2 marks: LHS) For the LHS of the equation, note that the number of ways to choose 3 students from the total of 3n students across both departments is ( 3n 3 ) . (2 marks: breaking RHS down into three cases) For the RHS of the equation, we partition the number of ways of forming a team (of 3 students picked from 3 different departments with n students each) into three possible cases as represented by the three terms on the RHS: 1. (2 marks: RHS first term) The first term considers the case where each student is picked from a different department. This is equivalent to constructing a 3-element list where there are n choices for each element, i.e., there are n× n× n = n3 possibilities. CISC 203: Discrete Mathematics for Computing II Problem Set 1 Solutions, Fall 2021 Page 6 2. (2 marks: RHS second term) The second term considers the case where all 3 students are picked from the same department. There are ( n 3 ) ways to pick 3 students from one department with n students. Since there are 3 departments to pick from, by the multiplication rule we have 3 · ( n 3 ) ways to pick the 3 students all from the same department. 3. (2 marks: RHS third term) The third term considers the following case: Suppose 2 students are picked from one department and 1 student is picked from another department. Since there are three departments, there are ( 3 2 ) = 3 ways to pick two out of the three departments, and 2 ways to choose which department to pick 1 student from vs. which department to pick 2 students from. By the multiplication rule, there are 3 × 2 = 6 ways to construct a list of 2 departments such that the first department will have 1 student chosen from it and the second department will have 2 students chosen from it. There are ( n 1 ) ways to pick one student from one department, and( n 2 ) ways to pick two student from one department. So, by the multiplication principle, there are 6 · ( n 1 )( n 2 ) ways to pick 1 student from one department and 2 students from another department. (2 marks: conclusion) Adding up the final values for the three cases above gives n3+3 · ( n 3 ) +6 · ( n 1 )( n 2 ) , which equals the RHS of the equation. Both the LHS and RHS give the correct answer to the counting problem, and thus we have proven the equation. 5.[12 marks] Suppose you wish to program an LED strip containing n LEDs (see sample image below) to light up each individual LED in red, green, blue, or white. How many length-n colour sequences have at least one pair of adjacent LEDs that light up with the same colour? Solution: (3 marks: number of sequences with no restrictions) First, we calculate the number of length-n colour sequences in the case that there are no restrictions on which LED can be assigned which of the four colours. In this case, we have a length-n sequence constructed from a pool of 4 elements (colours), with repetition allowed. So, there are 4n such sequences. Next, we calculate the number of length-n colour sequences where no two adjacent LEDs are assigned the same colour. Starting from the left-most LED, we can assign the colours to each individual LED as follows: • (2 marks) The first LED can be assigned any of the four colours • (2 marks) Each of the remaining n− 1 LEDs can be assigned one of 4− 1 = 3 colours, since they cannot reuse the same colour as the LED immediately to its left (2 marks) So, by the multiplication rule, the total number of length-n sequences where no two adjacent LEDs are assigned the same colour is 4× 3n−1. (3 marks) The total number of sequences in which there are at least two adjacent LEDs that are assigned the same colour is then 4n − 4× 3n−1.