[Math] How many positive integers less than $1000$ divisible by $3$ with sum of digits divisible by $7$

combinatoricsdivisibilityelementary-number-theory

How many positive integers less than $1000$ are divisible by $3$ with their sum of digits being divisible by $7$?

Well, I got Answer: $28$.

$a+b+c = 7k$ and $a,b,c$ are multiples of 3 so $a+b+c$ is a multiple of both $7$ and $3$.

Therefore $a+b+c=21$.

$(9-a)+(9-b)+(9-c)=6$

Then $^8C_2$. Can anyone explain why there is $9-a+9-b+9-c$?

If you have any other alternative method please explain?

Best Answer

Obviously the equation $(9-a)+(9-b)+(9-c)=6$ is equivalent to $a+b+c=21$, but there's a trick here. Now substitute $\alpha=9-a$, $\beta=9-b$, $\gamma=9-c$. Then the equation becomes $\alpha+\beta+\gamma=6$, still with the constraint that they are digits (ie numbers between $0$ and $9$ inclusive).

The trick here is that the later equation you don't have to bother with the constraint that they are $\le 9$ since that's implied by the equation. So the only constraint left to bother with is that they are integers $\ge 0$. This means that it's supposed to be easier to see that it's a triangle number $1+2+3+4+5+6+7=28$.

Otherwise of course the direct approach is doable too, but then you have to take into account that they must be $\le 9$ too. You see that this means that $0\le b+c\le 18$ so we must have $a = 21-b-c \ge 21-18 = 3$ (the other side doesn't matter as we have $a\le 9$). Then depending on $a$ you count the number of solutions to $b+c = 21-a$ and you'll get the same sum.

Of course if you have a lot of time or a computer you can simply list the numbers and count them.