Multiples

Printable View

October 30th 2009, 11:23 AM
Aquafina

Multiples

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?
October 30th 2009, 12:05 PM
Bruno J.

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.
October 30th 2009, 06:22 PM
Soroban

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.
October 30th 2009, 10:31 PM
Aquafina

Quote:

Originally Posted by Soroban

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