Find the number of positive integers not exceeding 1000 that are not divisible by 3 or 5

Printable View

- Sep 11th 2006, 11:13 PMsuedenationDivisibility
Find the number of positive integers not exceeding 1000 that are not divisible by 3 or 5

- Sep 12th 2006, 04:21 AMOReilly

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. - Sep 12th 2006, 06:29 AMThePerfectHacker
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 - Sep 12th 2006, 07:41 AMOReilly
- Sep 12th 2006, 08:51 AMtopsquark
I'm writing that one down. That's like, a cool theorem. (I may ask for a proof later...) :cool:

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... :) - Sep 12th 2006, 09:32 AMThePerfectHacker
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. - Sep 12th 2006, 10:45 AMtopsquark