Discrete Structures Homework

COT-3100, Assignment 3, Spring 2018

Due Date: 04/08/18 at 11:55 pm

Chapters 8 & 9: Relations, Counting and Probability

1. (8 points) Prove that the following relations are equivalence relations:

(a) R1 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)} on set {1, 2, 3}. (b) R2 = A

2 on any non-empty set A.

2. (12 points) Prove or disprove the following statements:

(a) Divisibility relation on the set of all non-zero integers is transitive.

(b) Divisibility relation on the set of all non-zero integers is an equivalence relation.

(c) Subset relation on the set of all sets is symmetric.

3. (10 points) On set A = {1, 2, 3, 4, 5}, define an equivalence relation whose equivalence classes partition A in the following way:{

{3, 2},{4, 1},{5} } .

Represent the relation using both the set-roster notation and a directed graph.

4. (10 points) Let R be an equivalence relation on set A. Prove the following equation:

∀a, b ∈ A, [a] = [b]

where [a] and [b] are the equivalence classes of a and b respectively (Hint: prove that [a] ⊆ [b] and [b] ⊆ [a]).

5. (15 points) Five persons a, b, c, d, e, and f want to sit at a round table with six chairs to have dinner. Answer the following questions using Multiplication Rule.

(a) In how many different ways can they sit at the table?

(b) In how many different ways can they sit at the table such that persons e and f sit on two adjacent chairs?

(c) In how many different ways can they sit at the table such that persons e and f don’t sit on the adjacent chairs?

1

6. (10 points)The mayor of city X wants to assign a unique identification number with n symbols to each person living in city X such that each symbol can be either a digit or one of the letters A, B, C, D, E, or F . Assuming that the population of city X is 16,800,000, what is the smallest possible value for n? (Hint: First find out how many different identification numbers can we make using n symbols; then use the Pigeonhole Principle to find an inequality for n).

7. (5 points) In a set of 150 integers, 120 of them are divisible by 3, 60 of them are divisible by 5, and 40 of them are divisible by 15. How many integers are divisible by neither 3 nor 5 (Hint: An integer is divisible by 15 iff it is divisible by both 3 and 5).

8. (15 points) Let n be a randomly chosen 7-digit positive integer.

(a) What is the probability that n is even?

(b) What is the probability that n ≥ 7, 000, 000? (c) What is the probability that 1, 500, 000 ≤ n ≤ 6, 200, 000? (d) What is the probability that n does not contain repeated digits and is not made

of digits 0 and 5?

(e) What is the probability that n has no repeated digits and is divisible by 5?

9. (15 points) In a box of 25 light bulbs, 15 of them are defective and the rest are working.

(a) In how many different ways can we pick 7 light bulbs from the box?

(b) If we randomly pick eight light bulbs, what is the probability of picking no defec- tive light bulbs?

(c) If we randomly pick nine light bulbs, what is the probability of picking five or seven defective light bulbs?

2