The inclusion-exclusion principle for RMO and IITJEE Maths

Reference: Combinatorial Techniques by Sharad Sane:

The principle and its applications:

The inclusion-exclusion principle, is among the most basic techniques of combinatorics. Suppose we have a set X with subsets A and B. Then, the number of elements that are in A or B (or both), that is, the cardinality of $A \cup B$ is given by $|A|+|B|- |A \cap B|$. The elements that are in both A and B were counted twice. To get rid of the over-counting, we must subtract. If $\overline{A}$ and $\overline{B}$ denote the complements of A and B respectively, then how many elements does the set $\overline{A} \cup \overline{B}$ have? This number is $|X|-|A|-|B|+|A \cap B|$. The explanation is as before. From the set of all the elements we get rid of those that are in A or B. In doing so, we subtracted the elements of $A \cap B$ twice. This has to be corrected by adding such elements once. Essentially, this way of over-counting (inclusion) correcting it using under-counting (exclusion) and again correcting (over-correcting) and so on is referred to as the inclusion-exclusion technique. As another example, consider the question of finding how many positive integers up to 100 are not divisible by 2, 3 or 5. We see that there are 50 integers that are multiple of 2, 33 that are multiples of 3 and 20 that are multiples of 5. This certainly amounts to over-counting as there are integers that are divisible by two of the given three numbers 2, 3 and 5. In fact, the number of integers divisible by both 2 and 3 is 16, the number of integers divisible by both 2 and 5, that is divisible by 10 is 10, the number of integers divisible by both 3 and 5 is the number of integers below 100 and divisible by 15 and that number is 6. Finally, the number of integers divisible by all three 2, 3, and 5 is just 3. Hence, the number of integers NOT divisible by any one of 2, 3 or 5 is $100-(50+33+20)+(16+10+6)-3=26$

The technique used above is called the sieve method. This technique was known to the Greeks and is in fact, known as the Sieve of Eratosthenes. (Remember: in high school, you have used this method to find primes from 1 to 100).

Also, note that I am reminded of the technique of telescoping series when I think about inclusion-exclusion. There seems to be some similarity in spirit.

More later,

Nalin Pithwa

This site uses Akismet to reduce spam. Learn how your comment data is processed.