Find the number of positive integers not exceeding 1000 that are not divisible by 3 or 5
There are 333 numbers that are divisible by 3 since 333*3=999.
Among those 333 numbers there are 66 numbers that are also divisble by 5 since 333/5 =66.6
So 333-66 = 267 numbers that are divisble only by 3.
There are 200 numbers that are divisible by 5 since 200*5 = 1000.
Among those 200 numbers there are 66 numbers that are also divisble by 3.
So 200-66 = 134 numbers that are divisible only by 5.
267 - numbers that are divisible only by 3.
134 - numbers that are divisible only by 5.
66 - numbers that are divisble both by 3 and 5.
So we have 267+134+66 = 467 numbers that are divisble either by 3 or 5.
1000-467 = 533 numbers that are not divisble either by 3 or 5.
Inclusion Exclusion Principle.
B be the set of all integers from 1 to 1000 divisible by 3
C be the set of all integers from 1 to 1000 divisible by 5
By the Inclusion Exclusion Principle we have,
|B u C|=|B| + |C| - |B n C|
|B n C| is the set of all numbers divisible by 3 and 5. Since gcd (3,5)=1 it is equivalent to saying divisible by 15.
Let us count number of such integers,
Or in more elegant form,
We can easily see 66 such integers exist
|B n C|=66.
You can easily find that,
|B u C|=333+200-66=467
Now let's see if I can give you a rep point, always a task of considerable uncertainty.
No joy on the rep. Sowwy! (Grumbles) Now I'll have to seriously consider giving Quick some...
That theorem is the mathematical side of the Venn Diagram.
In case you did not understand that crazy notation on Wikipedia heir is the general pattern.
|A u B u C|=|A| + |B| +|C| - |A n B|-|A n C|-|B n C|+|A n B n C|
If you have 4,
|A u B u C u D|=|A|+|B|+|C|+|D|-|A n B| -|A n C| -|A n D| -|B n C|- |B n D| - |C n D|+|A n B n C|+|A n B n D|+|A n C n D| +|B n C n D|-|A n B n C n D|
In general the number of terms is the sum of of binomials from 1 to n thus, it is, 2^n -1
Actually the result is easy to prove.
You need to Justify,
|A u B|=|A| + |B| -|A n B|
|A u B u C|=|A u (B u C)|=|A|+|B u C|-|A n B n C|
Get the idea, (just induction argument).
From here you should realize how it gets its name, Inculsion-Exclusion.