## 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 is given by . The elements that are in both A and B were counted twice. To get rid of the over-counting, we must subtract. If and denote the complements of A and B respectively, then how many elements does the set have? This number is . 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 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

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

### Like this:

Like Loading...

*Related*