Can this question be solved using combinatorics or permutations and combinations?

Question

How many positive integers less than $1000$ have the property that the sum of the digits of each such number is divisible by $7$ and the number itself is divisible by $3$?

This question has been before, but I saw a solution on Quora which intrigued me.

The solution is-

Thanks for the A2A

This is an awesome question i must say,

But i will make it easier for you. Its said the sum of digits should be divisible by $7$ as well as $3$. So sum of digits should be $21$. Only 1 possible case

So $(9-a) + (9-b) + (9-c) =21$.

We need to find whole number solutions to this

So, $a+b+c = 6$ , hence there will be ${}^8C_2$ possible numbers, or $28$ such numbers

Hope it helps

https://www.quora.com/How-many-positive-integers-less-than-1000-have-the-property-that-the-sum-of-the-digits-of-each-such-number-is-divisible-by-7-and-the-number-itself-is-divisible-by-3-1/answer/Atreya-Roy?share=8f02b880&srid=uYqRV

Can someone explain what he did?

Answer 1

It's a well known trick that a number is divisible by $3$ if and only if the sum of the digits is divisible by $3$. So saying the sum of the digits is divisible by $7$ and the number "itself" is divisible by $3$ is just an obscure way of saying the sum of the digits is divisible by $3$ and by $7$.

So the sum of the digits is divisible by $21$. The numbers are less than $1000$ so the sum of the digits is at the very most $9+9+ 9$. So the sum of the digits are divisible by $21$ but at most $27$ so (assuming we aren't counting $0$) the sum of the digits is exactly $21$.

So the question is simply. How many numbers less than 1000 have digits that add to $21$.

As $1000$ is obviously not one of them, the number can only have at most three digits, so the poster assumed the three digits were $(9-a),(9-b), (9-c)$ (where $a,b,c$ can be $0$ through $9$). So the sum of the digits is $9 -a + 9-b + 9-c = 21$.

Or in other words $a + b + c = 6$.

So the answer is the same as how many ways are there to chose $a,b,c$ from $0,1,2,....9$ where $a + b + c =6$.

At this point the poster assumes that answer is well known to be ${8 \choose 2}$

This is determined by the Stars and Bars method. To get $a + b + c= 6$, you can imagine you have six pebbles, and two divider. You can lay out $a$ pebbles and then place a divider. That indicates what $a$ is. Then you can lay out $b$ more pebbles and place the second divider. This indicates what $b$ is. You lay out the remaining pebbles (if any) and this indicates what $c$ is.

So you have $6+2=8$ positions, and you have chose $2$ positions to place the dividers and $6$ positions to place the pebbles and there are ${8 \choose 2}$ ways to do this and each one represents a way do choose $a + b + c = 6$.

So there are ${8\choose 2 } = \frac {8*7}2 = 28$ such numbers.

The range from

$a,b,c =(0,0,6)\mapsto 993$

$a,b,c =(0,1,5)\mapsto 984$

......

$a,b,c = (4,1,1)\mapsto 588$

$a,b,c = (4,2,0)\mapsto 579$

$a,b,c = (5,0,1)\mapsto 498$

$a,b,c = (5,1,0)\mapsto 489$

$a,b,c = (6,0,0)\mapsto 399$

Answer 2

To start off, the question states that the sum of the digits of the number is divisible by $7$. It also states that the number itself is divisible by $3$. There's a divisibility rule for $3$ which states that if a number is divisible by $3$, the sum of its digits will also be divisible by $3$. Since $3$ and $7$ are co-prime, we can say that the sum of the digits is then divisible by $3 \times 7 = 21$

In the next part, he says that the digits of the number are: $9 - a, 9 - b,$ and $9 -c$. Since the digits of a number range from $0$ to $9$, it's fine to think of the digits as he suggested, because $9 - a$ can take on the same range of values ($0$ to $9$) as just $a$. The one thing to be careful about here is that we need to make sure $9 - a$ does not equal $0$, which happens if $a = 9$, because this will mean our number is actually $2$ digits.

Now that we've chosen our digits to be $9 - a, 9 - b, 9 - c$, we take the sum of these and equate it to $21$. Rearranging a bit, we end up with $a + b + c = 6$. Take note that we eliminate the case that $a = 9$ now, and don't have to consider that case anymore.

Here, we can use the stars and bars method of combinatorics. Consider that there are $6$ stars that we need to distribute between $a, b, c$. We then need $3 - 1 = 2$ bars to distribute them. The total number of ways to distribute $6$ stars and $2$ bars is given as $6 + 2 \choose 2$ = $\frac{8!}{6!2!} = 28$