# Basic Combinatorics Inclusion-Exclusion Principle Clarification

1. Jun 14, 2010

### pupeye11

1. The problem statement, all variables and given/known data

How many integers between 1 and 2009, inclusive are (a) not divisible by 3,2, and 10 (b) not divisible by 3,2, or 10?

2. Relevant equations

The number of objects of the set S that have none of the properties is given by the alternating expression:

$$\mid S \mid -\sum \mid A_{i} \mid + \sum \mid A_{i} \cap A_{j} \mid - ....$$

The number of objects of S which have at least one of the properties is given by

$$\sum \mid A_{i} \mid - \sum \mid A_{i} \cap A_{j} \mid + ....$$

3. The attempt at a solution

Well i=1,2,3 where i=1 is the property that its divisible by 3 and i=2 for the property that its divisible by 2 and i=3 for the property its divisible by 10

$$\mid S \mid = 2009 \mid A_{1} \mid = 669 \mid A_{2} \mid = 1004 \mid A_{3} \mid = 200 \mid A_{1} \cap A_{2} \mid = 334 \mid A_{1} \cap A_{3} \mid = 66 \mid A_{2} \cap A_{3} \mid = 100 \mid A_{1} \cap A_{2} \cap A_{3} \mid = 66$$

So for the part a I thought it would be the first equation because I am looking for the number of objects that don't have all these properties at the same time so my answer came to 570.

For part b I thought it'd be the second equation which comes to 1439.

But shouldn't the number of integers that are not divisible by 3,2, and 10 be larger than the number of integers that are not divisible by 3,2, or 10?

2. Jun 14, 2010

### pupeye11

Ok, so pretty much I just had my two answers backwards. 570 is the answer to (b) by the first equation because I found an example and I did it the exact same way. Which makes part (a) equal to 1439 by the second equation. Correct?

3. Jun 14, 2010

### njama

(a) $$\sim{A_1} \cap \sim{A_2} \cap \sim{A_3}=\sim (A_1 \cup A_2 \cup A_3)=2009-1439=570$$

(b)$$\sim{A_1} \cup \sim{A_2} \cup \sim{A_3}=\sim (A_1 \cap A_2 \cap A_3)=2009-66=1943$$

4. Jun 14, 2010

### pupeye11

Don't you have those backwards though.

(a) not divisible by 3,2, and 10 which is just
$$\sim (A_1 \cap A_2 \cap A_3)=2009-66=1943$$

so obviously the 2009 - 66 would make sense here and

(b) not divisible by 3,2, or 10
would be the other method.

5. Jun 14, 2010

### njama

And what made you think that I did those backwards?

Regards.