Multiples

Aquafina · #1 $Old$ October 30th, 2009, 12:23 PM

Of the numbers 1, 2, 3, . . . , 6000, how many are not multiples of 2, 3 or 5?

My answers is:

3000 multiples of 2, 2000 multiples of 3, 1200 multiples of 5, 600 of 10, 1000 of 6, 400 of 15

So 4200 multiples, by adding the first 3 and subtracting the next 3 from the sum, since they have been counted twice.

So 6000 - 4200 = 1800.

Is this correct?

Bruno J. · #2 $Old$ October 30th, 2009, 01:05 PM

No! You have counted twice the numbers which are multiples of 2,3 and 5. So you should subtract 200 from your result.

One way to do it is to consider the intersection of the set of number which are not multiples of 2, the set of number which are not multiples of 3 and the set of number which are not multiples of 5.

So you would get $6000(1-1/2)(1-1/3)(1-1/5)=1600$ . If you expand the product you get :

$6000(-1/2-1/3-1/5+1/(2\times 3)+1/(2\times 5)+1/(3\times 5)-1/(2\times 3 \times 5))$

which is consistent with your approach by the inclusion/exclusion principle (once your small mistake is corrected).

Draw a Venn diagram, it might help you understand.

Soroban · #3 $Old$ October 30th, 2009, 07:22 PM

Hello, Aquafina!

We can use this fancy counting formula:

. . $n(A \cup B\cap C) \;=\;n(A) + n(B) + n(C)$
. . . . . . . . . . . . . . $- n(A \cap B) - n(B \cap C) - n(A \cap C)$
. . . . . . . . . . . . . . . . $+ n(A \cap B\cap C)$

Quote:

Of the numbers 1, 2, 3, ..., 6000, how many are not multiples of 2, 3 or 5?

We'll find the number of integers which are multiples of 2, 3 or 5.

. . $\begin{array}{cccc} \text{multiples of 2} & \frac{6000}{2} &=& 3000 \\ \\[-3mm] \text{multiples of 3} & \frac{6000}{3} &=& 2000 \\ \\[-3mm] \text{multiples of 5} & \frac{6000}{5} &=& 1200 \end{array}$ . . . $\begin{array}{cccc}\text{multiples of 2, 3} & \frac{6000}{6} &=& 1000 \\ \\[-3mm] \text{multiples fo 3, 5} & \frac{6000}{15} &=& 400 \\ \\[-3mm] \text{multiples of 2, 5} & \frac{6000}{10} &=& 600 \end{array}$ . . . $\begin{array}{cccc}\text{multiples of 2, 3, 5} & \frac{6000}{30} &=& 200 \end{array}$

$n(2\cup3\cup5) \;=\; n(2) + n(3) + n(5) - n(2\cap3) - n(3\cap5) - n(2\cap 5) - n(2\cap3\cap5)$

. . . . . . . $=\; 3000 + 2000 + 1200 - 1000 - 400 - 600 + 200$

. . . . . . . $= \;4400$

There are 4400 integers which are multiples of 2, 3 or 5.

Therefore, there are: . $6000-4400 \:=\: 1600$ which are not multiples of 2, 3 or 5.

Aquafina · #4 $Old$ October 30th, 2009, 11:31 PM

Quote:

Originally Posted by Soroban $View Post$

Hello, Aquafina!

We can use this fancy counting formula:

. . $n(A \cup B\cap C) \;=\;n(A) + n(B) + n(C)$
. . . . . . . . . . . . . . $- n(A \cap B) - n(B \cap C) - n(A \cap C)$
. . . . . . . . . . . . . . . . $+ n(A \cap B\cap C)$

$n(2\cup3\cup5) \;=\; n(2) + n(3) + n(5) - n(2\cap3) - n(3\cap5) - n(2\cap 5) - n(2\cap3\cap5)$

. . . . . . . $=\; 3000 + 2000 + 1200 - 1000 - 400 - 600 + 200$

. . . . . . . $= \;4400$

Hi, do the multiples of 2,3 and 5 have to be added or subtracted? You have used both operations...

Looking at the inclusion/exclusion principle Bruno J posted, I am able to do the question when thinking about the Venn Diagram