4
$\begingroup$

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?!!

$\endgroup$
  • 2
    $\begingroup$ In the first one you have double counted those sets where both $a$ and $b$ are divisible by 5. $\endgroup$ – Nate Jun 10 '14 at 22:43
  • $\begingroup$ @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? $\endgroup$ – math.n00b Jun 10 '14 at 22:50
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – math.n00b Jun 10 '14 at 23:11
  • $\begingroup$ It happens. :-) $\endgroup$ – Eric Towers Jun 10 '14 at 23:14
3
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.