Find the number of $2$-element subsets $\{a,b\}$ of $\{1,\cdots,1000\}$ such that $5 \mid a\cdot b$

Well, I have thought of two different solutions giving contradictory results, obviously one of them is wrong, or maybe both are wrong, but I can't see why. Please help me find the logical flaws or counting mistakes in my arguments.

The first alleged solution:

Since $5$ is a prime number, then $5 \mid a$ or $5 \mid b$. Without loss of generality, assume that $5 \mid a$. There are $200$ numbers in $\{1,\cdots,1000\}$ that are divisible by $5$. So, we have $200$ choices for $a$. On the other hand, the other number can be anything that we want, except $a$, because in that case the subset will be a singleton. So, we have $999$ choices for $b$. Therefore, there are $200 \times 999=199800$ such subsets.

The second alleged solution:

There are $200$ numbers that are divisible by $5$ in $\{1,\cdots,1000\}$. To find a $2$-element subset such that the product of its two elements is divisible by $5$ we can find the number of all $2$-element subsets such that the product of its elements is not divisible by $5$ and subtract this quantity from the number of $2$ element subsets of $\{1,\cdots,1000\}$: $${1000 \choose 2} - {800 \choose 2} = \frac{1000(999)}{2} - \frac{800(799)}{2}=179900$$

Why these two numbers don't match? Aren't they supposed to be equal?!!

• In the first one you have double counted those sets where both $a$ and $b$ are divisible by 5. – Nate Jun 10 '14 at 22:43
• @Nate: Yes, I guessed that, but I don't see how those $199800-179900=19900$ extra elements are counted twice. Is it possible to remedy the first one into something correct and meaningful? – math.n00b Jun 10 '14 at 22:50

As Nate says in the comments: the sets where both $a$ and $b$ are divisible by 5 are counted twice as both numbers can play the role of $a$.

In order to correct for this we simply have to subtract off the number of these double counts which is the number of pairs $\{a,b\}$ with $a$ and $b$ divisible by 5 which is $$\binom{200}{2} = 19900$$ as you have noticed that there are 200 elements divisible by 5. When we have done this the answers then do agree and so both approaches are perfectly reasonable.

When $5|a$, $5|b$, and $a \neq b$, both $(a,b)$ and $(b,a)$ are double counted in $200 \times 999$. There are $200 \times 199$ of these twice counted pairs, so subtracting off half of these, $100 \times 199 = 19900$, will correct the count.

• I like both answers equally. I like this one because it needs nothing more than simple primary school type arithmetic to understand it but I chose the other answer only because it had been posted 8 seconds earlier. Thank you. – math.n00b Jun 10 '14 at 23:11
• It happens. :-) – Eric Towers Jun 10 '14 at 23:14

Let $U = \{1,2,...,1000\}$, and $A = \{\{a,b\}: (a,b) \in U^2,5|a, 5\not|b\}$, $B = \{\{a,b\}: (a,b) \in U^2, 5|a, 5|b\}$, and $C = \{\{a,b\}: (a,b) \in U^2, 5|ab\}$. Then:

$C = A\cup B$, and $A$, $B$ are disjoint. Thus:

$|C| = |A| + |B| = \binom{200}{1}\cdot \binom{800}{1}+ \binom{200}{2} = 179,900$.

• Where does that $8 \choose 1$ come from? and I guess you're missing $900$ subsets in your answer. – math.n00b Jun 10 '14 at 23:25