2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I'd rather say that $(9-a)+(9-b)+(9-c)=6$ $\endgroup$ – Hagen von Eitzen Aug 22 '17 at 6:01
  • $\begingroup$ @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$. $\endgroup$ – skyking Aug 22 '17 at 6:28
  • $\begingroup$ I see. I have retracted my duplicate vote. $\endgroup$ – Siong Thye Goh Aug 22 '17 at 6:30
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.