Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CISC 203: Discrete Mathematics for Computing II

Problem Set 1

2021

[15 marks]   1.   (a) Prove A × (B ∩ C) = (A × B) ∩ (A × C) using Proof Template 5. Hint: See pages 60-63 for some

examples of how to do this kind of proof. Note that instead of considering an element x, you will need to consider an element (x,y) due to the Cartesian product.

(b) For A = {a ∈ R : |a − 1| ≤ 2} and B = {b ∈ R : |b − 4| ≤ 2}, describe the set A and the set B

in words (i.e., define which elements they each contain) and clearly plot all the elements of the set (A × B) on an xy-plane.

(c) Let n ∈ N and n > 0, and let the set

and prove your answers using an appropriate proof technique.

[17 marks] 2.   (a) Let A = {a,b,c,d,e,f,g,h} and let R be an equivalence relation on A such that a R c, c R d, d R g , and b R h. Assume that there are four distinct equivalence classes resulting from R. Determine:

• The equivalence classes resulting from R.

• All elements (i.e., ordered pairs) of R

(b) Let B = {2n  : n ∈ Z} and let R be a relation defined on the set R+  (i.e., positive real numbers) such that x R y if ∈ B. Is R an equivalence relation? Show your work.

[13 marks] 3.   (a) A group of 120 students were surveyed to see what computer games they play, and the following results were obtained:

• 46 students play DOTA2

• 52 students play CS:GO

• 50 students play TF2

• 25 students play both DOTA2 and CS:GO

• 21 students play both DOTA2 and TF2

• 23 students play both CS:GO and TF2

• 16 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, e.g., with union and intersection operations.

(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.

[14 marks] 4. 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

[12 marks] 5. Suppose that a website requires you to select a password containing exactly n characters. Each character may be an upper-case letter, lower-case letter, or numeric digit.  The password requires that any two adjacent characters in the password cannot be the same.

To illustrate, you may consider the following two examples:  If the website requires an 11-character password (i.e., n = 11), the password imperial233 is not allowed (since it contains the sequence 33) but the password stormcloak3 is allowed (even though it contains the character o twice).

How many disallowed n-character passwords are there? Show all your steps and explain them in a similar level of detail as the examples in the notes, e.g., explain as if you are teaching someone how to solve the problem (marks will be assigned accordingly).