Positive integers a, b, and c are randomly and independently selected with replacement from the set $\{1, 2, 3, \dots, 2010\}$. What is the probability that $abc + ab + a$ is divisible by 3?

This is how I tried to approach it:

$abc + ab + a$ can be factored as $a(bc + b + 1)$

Thus, for $abc + ab + a$ to be divisible by $3$, all that needs to be true is $a$ is divisible by 3.

There are $2010/3 = 670$ numbers from $1 ... 2010$ thare are divisible by $3$. These are the possible choices for $a$

$b$ and $c$ can be anything and there are $2010$ choices for each.

Thus the probability is $\frac{670\cdot 2010\cdot 2010}{2010\cdot 2010\cdot 2010}$ which simplifies to $\frac{1}{3}$.

However, apparently my solution is incorrect. Where did I go wrong?

EDIT: I forgot about the case where $bc + b + 1$ could be divisible by 3. How do you solve it then?

  • 4
    $\begingroup$ What if $a$ isn't divisible by $3$, but $bc+b+1$ is? $\endgroup$ – Daniel Fischer Dec 11 '13 at 3:15
  • $\begingroup$ Oh - how do you solve it then? $\endgroup$ – 1110101001 Dec 11 '13 at 3:47
  • $\begingroup$ Count how many ways $bc+b+1$ can be a multiple of $3$. $b$ cannot be a multiple of $3$ then. If $b \equiv 1 \pmod{3}$, then $c$ must be ... . If $b \equiv 2 \pmod{3}$, then $c$ must be ... . $\endgroup$ – Daniel Fischer Dec 11 '13 at 3:51
  • $\begingroup$ ... And don't double count. $\endgroup$ – Dale M Dec 11 '13 at 7:07

First of all, whether any polynomial expression in $a,b,c$ is divisible by $3$ or not depends only upon the residue classes of $a,b,c$ modulo $3$. Because $2010$ is a multiple of $3$, each of $a,b,c$ has exactly a $\frac13$ probability of being congruent to $0,1,2\pmod 3$. So you'll get the same answer by just restricting each of $a,b,c$ to the values $0,1,2$, independently and each with probability $\frac13$.

At this point you could just do it by brute force. But: $abc+ab+a$ is not divisible by $3$ if and only if both $a$ is not divisible by $3$ and $bc+b+1$ is not divisible by $3$. The events are independent, and the first event has probability $\frac23$. For the second event, either brute force or: $b=0$ works no matter what $c$ is, while each of $b=1$ amd $b=2$ works for two values of $c$. So the second event has probability $\frac79$, yielding the final probability of $\frac23 \frac79$. In other words, $abc+ab+a$ is divisible by $3$ with probability $1-\frac23\frac79 = \frac{13}{27}$.

  • $\begingroup$ Nice way of doing it without brute force! $\endgroup$ – 1110101001 Dec 11 '13 at 5:11

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.