Thread: Divisibility

Originally Posted by suedenation

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.

Originally Posted by suedenation

Find the number of positive integers not exceeding 1000 that are not divisible 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

Originally Posted by ThePerfectHacker

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

Elegant solution, better then mine. I like it.

I thought also of counting numbers divisible by 15.

Originally Posted by ThePerfectHacker

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.

Originally Posted by ThePerfectHacker

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.

Oh! I see it now. Kinda silly of me not to have seen it before. (The Venn diagram comment was what I needed, thank you!)

-Dan