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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: