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.
Here is an excellent demonstration of the Inclusion Exclusion Principle.
Let
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|
Now,
|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,
15,30,45,...,990
Or in more elegant form,
15(1),15(2),15(3),...,15(66)
We can easily see 66 such integers exist
Thus,
|B n C|=66.
You can easily find that,
|B|=333
|C|=200
Thus,
|B u C|=333+200-66=467
I'm writing that one down. That's like, a cool theorem. (I may ask for a proof later...)
Now let's see if I can give you a rep point, always a task of considerable uncertainty.
-Dan
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|
Then,
|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.