Finding the numbers having a particular factor,an upper limit and a specific set of digits.

Question

Question :

How many numbers less than $50000$ can be formed which are multiples $6$ using the digits $0,1,2,3,4,5$?

My attempt :

First of all, for a number to be a multiple of $6$, it should be a multiple of $2$ as well as $3$. So, the number must be even as well as it's sum of digits should be a multiple of $3$. Next, the number should have only the digits $1,2,3,4$ in the first position as it has to be less that $50000$. But, I face a problem, If I put $2$ or $4$ in the first position, then I will have one less even digit for the last position and there would be cases where I only use the digits $0,1,2,4,5$ or $1,2,3,4,5$ so as to make the number divisible by $3$. So, is there an efficient way to cover all the cases and get the answer quickly?

All help will be appreciated.

Answer 1

I assume leading zeros are not allowed, but you can adapt this if they are.

If you have to use the digits once each, the one you don't use has to be $0$ or $3$ to get a multiple of $3$. Then you just need a permutation where the ones digit is even and the first digit is not zero. I would choose which digit is missing, condition on whether the first digit is even or odd, then count the ways to choose the ones digit, then the number of ways to choose each other digit.

If you can use the digits multiple times, choose the ones digit as an even, choose the first digit as non-zero, choose three others as anything, then note that you have two choices for the last digit to make the multiple of $3$ come out right.

Answer 2

We put it in three cases as the last digit must be either $0;2$ or $4.$ (I assume that you can use each digit only once).

First case: The number is in the form $\overline{abcd0}$, which means the numbers $a,b,c,d$ are $4$ of the remaining numbers available $(1;2;3;4;5)$.

There are $5$ ways of picking four numbers from this set, we add $a,b,c,d$ along with $e$ for each pick:

$1+2+3+4+0=10$, not divisible by $3$.

$1+2+3+5+0=11$, not divisible by $3$.

$1+2+4+5+0=12$, divisible by $3$.

$1+3+4+5+0=13$, not divisible by $3$.

$2+3+4+5+0=14$, not divisible by $3$.

We conclude that $(a,b,c,d)$ must be a permutation of $(1;2;4;5)$ that satisfy $a<5$.

For each sub-case $a=1;a=2;a=4$, note that $(b,c,d)$ is a permutation of $3$ remaining numbers in the set, so each sub-case will have $3!=6$ possible outcomes for $b,c,d$.

In total, this first case (including $3$ sub-cases) should have $6 \times 3=18$ satisfied numbers.

Second case: The number is in the form $\overline{abcd2}$, which means the numbers $a,b,c,d$ are $4$ of the remaining numbers available $(0;1;3;4;5)$.

There are $5$ ways of picking four numbers from this set, we add $a,b,c,d$ along with $e$ for each pick:

$0+1+3+4+2=10$, not divisible by $3$.

$0+1+3+5+2=11$, not divisible by $3$.

$0+1+4+5+2=12$, divisible by $3$.

$0+3+4+5+2=14$, not divisible by $3$.

$1+3+4+5+2=15$, divisible by $3$.

We conclude that $(a,b,c,d)$ must be a permutation of $(0;1;4;5)$ or $(1;3;4;5)$ that satisfy $a<5$ and $a\ne 0$.

• Case 2.1: $(a,b,c,d)$ is a permutation of $(0;1;4;5)$ that satisfy $a<5$ and $a\ne 0$. There are two sub-cases for this one ($a=1;a=4$), plus each sub-case has $6$ possible outcomes for $b,c,d$, so there are $6 \times 2 =12$ satisfied numbers.

• Case 2.2: $(a,b,c,d)$ is a permutation of $(1;3;4;5)$ that satisfy $a<5$ and $a\ne 0$. There are three sub-cases for this one ($a=1;a=3;a=4$), plus each sub-case has $6$ possible outcomes for $b,c,d$, so there are $6 \times 3 =18$ satisfied numbers.

So the second case should have a total of $12+18=30$ satisfied numbers.

Third case: The number is in the form $\overline{abcd4}$, this is similar to the second case, you can do it by yourself, after finishing it you can check the answer below.

There are $78$ five-digit numbers less than $50000$ divisible by $6$ and can be formed by using the digits $(0;1;2;3;4;5)$

I think you should do similarly for the case one, two, three, four digit numbers, so here are two extra hints to do them:

The number of ways to choose $k$ objects from $n$ objects, which the order does not matter, is: $$\frac{n!}{k!(n-k)!}$$ For this problem the order of choosing numbers is important, so the number of permutations of $n$ distinct objects is $n!$.

I don't think this is a quick way, but it will surely help you to get the correct answer.

Answer 3

In the case that the digits can be repeated, thereby including those with trailing zeros like $00012$, and including $00000$,
then we are looking for the number of integer solutions to $$ \left\{ \matrix{ 0 \le x_{\,k} \le 5 \hfill \cr y = 0,2,4 \hfill \cr x_{\,1} + x_{\,2} + x_{\,3} + x_{\,4} + y = 3k\quad \left| {\;0 \le k \le 24/3} \right. \hfill \cr} \right. $$ i.e. $$ \left\{ \matrix{ 0 \le x_{\,k} \le 5 \hfill \cr x_{\,1} + x_{\,2} + x_{\,3} + x_{\,4} = s = 3k - 2j\quad \left| \matrix{ \;0 \le k \le 8 \hfill \cr \;0 \le j \le 2 \hfill \cr} \right. \hfill \cr} \right. $$

Now $$N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = s \hfill \\ \end{gathered} \right.$$ as explained in this other related post is given by $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s} {r}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m \hfill \\ k \hfill \\ \end{gathered} \right)\left( \begin{gathered} s + m - 1 - k\left( {r + 1} \right) \\ s - k\left( {r + 1} \right) \\ \end{gathered} \right)} $$ Then $$ \sum\limits_{0\, \le \,\,k\,\, \le \,8} {\sum\limits_{0\, \le \,\,j\,\, \le \,2} {N_b (3k - 2j,5,4)} } = 1296 $$ including $00000$, but also $50,004,\;\cdots,\; 55,554$.

So we have to deduct from the above the solutions to $$ \left\{ \matrix{ 0 \le x_{\,k} \le 5 \hfill \cr x_{\,1} + x_{\,2} + x_{\,3} + 5 = s = 3k - 2j\quad \left| \matrix{ \;0 \le k \le 8 \hfill \cr \;0 \le j \le 2 \hfill \cr} \right. \hfill \cr} \right. $$ i.e. $$ \left\{ \matrix{ 0 \le x_{\,k} \le 5 \hfill \cr x_{\,1} + x_{\,2} + x_{\,3} = s = 3k - 2j - 5\quad \left| \matrix{ \;0 \le k \le 8 \hfill \cr \;0 \le j \le 2 \hfill \cr} \right. \hfill \cr} \right. $$ giving $$ \sum\limits_{0\, \le \,\,k\,\, \le \,8} {\sum\limits_{0\, \le \,\,j\,\, \le \,2} {N_b (3k - 2j - 5,5,3)} } = 216 $$ ($50,000$ is not divisible by $6$)

Thus the final result is $1080$ , which is confirmed by a brute force calculation.