# Count the the number of elements in a set, exactly divisible by 2 out of 3 numbers

I need a hint to solve the following problem, in a way that a 10yr old child can understand.

On a blackboard, all whole numbers from 1 to 2006 were written. John underlined all numbers divisible by 2, Adam underlined all numbers divisible by 3 and Peter underlined all numbers divisible by 4. How many numbers were underlined exactly twice?

-
@experimentX but also the even numbers divisble by 3 right (such as 6). – JohnPhteven Dec 27 '12 at 13:27
@ZafarS sorry, yes you are right!! – Santosh Linkha Dec 27 '12 at 13:29

For a $10$-year old child, (or a substantially older mathematician), a useful way to begin is by experimenting. The problem is about undelining integers. So write down a fairly long initial string $1,2,3,4,5,\dots$ of natural numbers, and start underlining.

After a while, possibly with guidance, it may be discovered that the numbers $1$ to $12$ have $3$ "doubles," and that the underlining pattern starts all over again at $13$. Every full group of $12$ contributes $3$ doubles. So about $1/4$ of our $2006$ numbers should be doubles.

More precisely, the last full group of $12$ ends at $2004$, and neither $2005$ nor $2006$ is a double. So the number of doubles is one-quarter of $2004$.

-
Nice! Just correct the numbers of "doubles" in the group of 12 to 3. – gd047 Dec 27 '12 at 15:18
@gd047: Thanks for the correction! The serious point I wanted to make is that we must "get our hands dirty." The only kind of problem for which we don't need to do that is a problem close to one whose solution we have seen before. – André Nicolas Dec 27 '12 at 15:37

First, in order for a number to be underlined twice, it must be even (since it must be divisible by $2$ or $4$). There are are $1003$ such numbers. Every number in this list is even. For a number to be underlined twice, it is either divisible by $2$ and $4$ or $2$ and $3$.

The numbers in our list are $\{2(1), 2(2), ..., 2(1003)\}$. In order for a number to be divisible by $2$ and $4$, it must be $2(n)$, where $n \in \{1, ... , 1003\}$ is even. Exactly two thirds of those numbers will additionally not be divisible by $3$. How many of those are there?

In order for a number to be divisible by $2$ and $3$, it must be of the form $2(n)$, where $n \in \{1, ... , 1003\}$ is a multiple of $3$. Exactly one third of numbers in $\{1,...,1003\}$ are multiples of $3$. Additionally, $n$ must be odd (else 2n is divisible by $4$ as well). How many odd multiples of $3$ are in $\{1, ..., 10003\}$?

-
1. 4 itself is divisible by 2, so all numbers divisible by 4 are divisible by 2.

2. All even numbers divisible by 3 (for example, 6, 18) are underlined more than once, since even numbers are divisible by 2.

3. Then you just got to subtract the numbers which are divisible by both 4 and 3, for example 24 and 12 (since if they are divisible by 4 (and 2) and 3, they are underlined thrice.

-
But the question wants those which were underlined exactly twice. If a number is divisible by 2, 3, and 4, it doesn't meet this criteria (12, for example) because it will be underlined 3 times. You need to discard those numbers. – anonymous Dec 27 '12 at 13:33
Oh, I read over that part. So that just means every even number divisible by 3 but not by 4. – JohnPhteven Dec 27 '12 at 13:36
So, how many of them are underlined exactly twice? – gd047 Dec 27 '12 at 13:49
@gd047 That is for you to figure out. You asked for a hint, not for the answer. If you're having trouble just follow my steps (or anonymous' steps in the other answer) and you'll get there.. – JohnPhteven Dec 27 '12 at 13:50
Divisible by 4 are 501. All even numbers divisible by 3 are 334. Divisible by both 4 and 3 are 167. But the answer in not 501+334-167 – gd047 Dec 27 '12 at 14:07