Inclusion and exclusion
Task number: 3841
Consider a task to determine, how many of numbers from the interval \( \{1,\dots,100 \} \) have a nontrivial common divisor with the number 660.
The solution leads to the calculation of the size of union of several sets, for which the principle of inclusion and exclusion can be applied. PIE expresses the size of the union as the sum of the sizes of suitable intersections multiplied by the appropriate signs.
For the above problem, decide how many summands in this sum will be non-zero, or in other words how many considered intersections will be non-empty.
- 12
- 15
- 16
Solution
The number 660 has the following prime divisors: 2, 3, 5, and 11, which leads to a PIE with four sets: products of different subsets of these four primes.
The term for PIE therefore has 15 summands. Some intersections will be empty, in particular when the product of the corresponding primes is greater than 100. Namely, these cases are: \( 2 {\cdot} 5 \cdot 11 \), \( 3 {\cdot} 5 \cdot 11 \), \( 2 {\cdot} 3 \cdot 5 {\cdot} 11 \).
Answer
The correct answer is a.
