Answer to Question #175237 in Discrete Mathematics for kislay

Question

Find the number of integers between 1 and 300 both inclusive that are divisible by the

following types:

(i). at-least one of 3, 5, 7.

(ii). 3 and 5 but not 7.

(iii). 5 but neither 3 nor 7

Answer 1

Solution:

Let

$\begin{array}{l} A=\{n \in Z \mid(1 \leq n \leq 300) \wedge(3 \mid n)\} \\ B=\{n \in Z \mid(1 \leq n \leq 300) \wedge(5 \mid n)\} \\ C=\{n \in Z \mid(1 \leq n \leq 300) \wedge(7 \mid n)\} \end{array}$

Then,

$\begin{array}{l} |\mathrm{A}|=\lfloor 300 / 3\rfloor=100 \\ |\mathrm{~B}|=\lfloor 300 / 5\rfloor=60 \\ |\mathrm{C}|=\lfloor 300 / 7\rfloor=42 \end{array}$ ...(i)

(i) We need to find $|A \cup B \cup C|$

By the principle of inclusion-exclusion

$|\mathrm{A} \cup \mathrm{B} \cup \mathrm{C}|=|\mathrm{A}|+|\mathrm{B}|+|\mathrm{C}|-[|\mathrm{A} \cap \mathrm{B}|+|\mathrm{A} \cap \mathrm{C}|+|\mathrm{B} \cap \mathrm{C}|]+|\mathrm{A} \cap \mathrm{B} \cap \mathrm{C}|$

Using (i),

$\begin{aligned} |\mathrm{A}|=\lfloor 300 / 3\rfloor=100 & &|\mathrm{~A} \cap \mathrm{B}|=\lfloor 300 / 15\rfloor=20 \\ |\mathrm{~B}|=\lfloor 300 / 5\rfloor=60 & &|\mathrm{~A} \cap \mathrm{C}|=\lfloor 300 / 21\rfloor=100 \\ |\mathrm{C}|=\lfloor 300 / 7\rfloor=42 & &|\mathrm{~B} \cap \mathrm{C}|=\lfloor 300 / 35\rfloor=8 \\ & &|\mathrm{~A} \cap \mathrm{B} \cap \mathrm{C}|=\lfloor 300 / 105\rfloor=2 \end{aligned}$

$\therefore |A \cup B \cup C|=100+60+42-(20+14+8)+2=162$

(ii) We need to find $|(A \cap B)-C|$

By the definition of set-minus:

$|(A \cap B)-C|=|A \cap B|-|A \cap B \cap C|=20-2=18$

(iii) We need to find $|B-(A \cup C)|$

Now, $|B-(A \cup C)|=|B|-|B \cap(A \cup C)|$

Distributing B over the intersection

$\begin{aligned} |B \cap(A \cup C)| &=|(B \cap A) \cup(B \cap C)| \\ &=|B \cap A|+|B \cap C|-|(B \cap A) \cap(B \cap C)| \\ &=|B \cap A|+|B \cap C|-|B \cap A \cap C| \\ &=20+8-2=26 \end{aligned}$

Thus, $|B-(A \cup C)|=|B|-|B \cap(A \cup C)|=60-26=34$