Inclusion-Exclusion Calculator

Consider the following problem:

"Find how many integers divisible by 2 and 5 there are between 0 and 100."

To solve this problem, we use the inclusion-exclusion principle.

Calculator
Calculate \(|\bigcup_{i \in I}D_{i}|\) ,where \(D_{k}\) is the set of all integers divisible by \(k\) (from \(a\) to \(b\))
\(I\) \(=\)
Enter one or more positive integers. E.g. "2, 3, 5"
\(a\) \(=\)
Enter a positive integer
\(b\) \(=\)
Enter a positive integer greater than \(a\)

We use the notation \(D_n\) to denote the set of integers divisible by \(n\). For example, \(D_4= \{4, 8, 12, ... \}\).

The inclusion-exclusion principle says that: \(|\bigcup_{i \in I} \space D_i| = \sum_{i \in I} \space |D_i| - \sum_{i, j \in I: i < j} \space |D_i \cap D_j| + ... + (-1)^{n-1} \space |D_i \cap D_j \cap ... \cap D_k| \).

In our problem, we have to find \( |D_2 \cup D_5| \) between 1 and 100. So, for two sets, the above principle will look like this:

\( |D_2 \cup D_5| = |D_2| + |D_5| - |D_2 \cup D_5| \)

We have two find \( |D_2| \), \(|D_5|\) and \(|D_2 \cup D_5|\). It is rather easy to see that there are exactly \( \lfloor (100 \div 2) \rfloor \) integers divisible by 2 between 0 do 100. Generally, \( |D_k| = \lfloor (b - a) \div k \rfloor\), where \(a\) is the lower limit and \(b\) is the upper limit.

So \( |D_2| = 50\) and \( |D_5| = 20 \).

What about \(|D_2 \cup D_5| \)? It is the set of integers divisible by both 2 AND 5. It can be noticed that \(|D_2 \cup D_5| = |D_{2 \times 5}| \). So, \(|D_2 \cup D_5| = \lfloor (100 \div 10) \rfloor = 10\).


»