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

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?

• I'd rather say that $(9-a)+(9-b)+(9-c)=6$ – Hagen von Eitzen Aug 22 '17 at 6:01
• @SiongThyeGoh I'm not sure it's a duplicate. This question is about the solution itself of that. Why you'd consider $(9-a)+(9-b)+(9-c)=6$ instead of $a+b+c=21$. – skyking Aug 22 '17 at 6:28
• I see. I have retracted my duplicate vote. – Siong Thye Goh Aug 22 '17 at 6:30

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.

The digit sum has to divisible by $3$ and by $7$, hence by $21$. This implies that we have to deduct a total of $6$ points from the maximal possible $9+9+9=27$. By stars and bars these $6$ points can be distributed in ${8\choose 2}=28$ ways onto the three decimal places.

A number is divisible by $3$ iff the sum of its digits (in the decimal representation) is divisible by $3$. Since $3$ and $7$ are coprime, the problem boils down to finding the number of non-zero triples $(a,b,c)$ such that $a,b,c\in\{0,1,2,\ldots,9\}$ and $21\mid a+b+c$. $a+b+c$ is at most $27$, hence the problem is equivalent to finding the non-zero triples $(a,b,c)$ with $a,b,c\in\{0,1,2,\ldots,9\}$ and $a+b+c\color{blue}{=}21$. The answer is given by $$[x^{21}](1+x+x^2+\ldots+x^9)^3 = [x^{21}]\frac{(1-x^{10})^3}{(1-x)^3}$$ where $[x^k]\,f(x)$ stands for the coefficient of $x^k$ in the Taylor/Laurent series of $f(x)$ at the origin.
Since $\frac{1}{(1-x)^3}=\sum_{m\geq 0}\binom{m+2}{2}x^m$ and $(1-x^{10})^3 = 1-3x^{10}+3x^{20}-x^{30}$, the previous number equals

$$\binom{21+2}{2}-3\binom{11+2}{2}+3\binom{1+2}{2}=28$$ so there are $\color{blue}{28}$ numbers in $\{1,2,\ldots,999\}$ whose digit sum is a multiple of both $3$ and $7$.