Pre-interview_Test_Question_45

Screenshot 2020-07-05 at 23.24.22

Let A be the set of natural numbers less than or equal to 6000 that are multiples of 2. Similarly B for multiples of 3, C for multiples of 5. We want to work out:

\displaystyle |(A \cup B \cup C)^c| = 6000 - |A \cup B \cup C|

We first work out |A \cup B| for general sets A and B. We can start with |A| + |B|, but we have counted those numbers in the intersection of A and B exactly twice (and the others once), so |A \cup B| = |A| + |B| - |A \cup B|. (a Venn diagram may be useful for seeing this)

To find |A \cup B \cup C|, write:

\begin{align*}|A \cup B \cup C| & = |A \cup (B \cup C)| \\ & = |A| + |B \cup C| - |A \cap (B \cup C)| \\ & = |A| + |B| + |C| - |B \cap C| - |(A \cap B) \cup (A \cap C)| \\ & = |A| + |B| + |C| - |B \cap C| - |A \cap B| - |A \cap C| + |A \cap B \cap C| \end{align*}

It just remains to find these six cardinalities for the three sets we have here.

We clearly have:

\displaystyle |A| = \frac {6000} 2 = 3000

\displaystyle |B| = \frac {6000} 3 = 2000

\displaystyle |C| = \frac {6000} 5 = 1200

Note that the elements of A \cap B are the multiples of 2 and 3, that is the multiples of 6, so:

\displaystyle |A \cap B| = \frac {6000} 6 = 1000

Similarly, the elements of A \cap C are the multiples of 2 and 5, the multiples of 10, so:

\displaystyle |A \cap C| = \frac {6000} {10} = 600

The elements of B \cap C are the multiples of 3 and 5, the multiples of 15, so:

\displaystyle |B \cap C| = \frac {6000} {15} = 400

Finally, the elements of A \cap B \cap C are the multiples of 2, 3 and 5, the multiples of 30 so:

\displaystyle |A \cap B \cap C| = \frac {6000} {30} = 200

So:

|A \cup B \cup C| = 3000 + 2000 + 1200 - 1000 - 600 - 400 + 200 = 4400

So there are 1600 numbers less than or equal to 6000 that are not multiples of 2, 3 or 5.

Factlet: By induction, you can establish for a formula for \displaystyle \left|\bigcup_{i = 1}^n A_i\right| for some collection of n sets \langle {A_i}\rangle. This is called the inclusion exclusion principle. https://en.wikipedia.org/wiki/Inclusion–exclusion_principle

2 Likes

Love this Factlet!