GATE CS 2017 Set 1 Q47 — Sets, Relations and Functions

We can solve this using the Principle of Inclusion-Exclusion (PIE).

Let $U = \{1, 2, \dots, 500\}$ be the universal set. Let $A$, $B$, and $C$ be the subsets of $U$ containing integers divisible by $3$, $5$, and $7$ respectively.

The number of elements in each set is calculated as follows:

• $|A| = \lfloor \frac{500}{3} \rfloor = 166$
• $|B| = \lfloor \frac{500}{5} \rfloor = 100$
• $|C| = \lfloor \frac{500}{7} \rfloor = 71$

Now, we find the pairwise intersections using the least common multiple (LCM) of the divisors:

• $|A \cap B| = \lfloor \frac{500}{\text{lcm}(3,5)} \rfloor = \lfloor \frac{500}{15} \rfloor = 33$
• $|B \cap C| = \lfloor \frac{500}{\text{lcm}(5,7)} \rfloor = \lfloor \frac{500}{35} \rfloor = 14$
• $|C \cap A| = \lfloor \frac{500}{\text{lcm}(7,3)} \rfloor = \lfloor \frac{500}{21} \rfloor = 23$

The intersection of all three sets is:

• $|A \cap B \cap C| = \lfloor \frac{500}{\text{lcm}(3,5,7)} \rfloor = \lfloor \frac{500}{105} \rfloor = 4$

Applying the Principle of Inclusion-Exclusion: