# How many five digit numbers divisible by $3$ can be formed using the digits $0,1,2,3,4,7$ and $8$ if each digit is to be used at most once

How many five digit numbers divisible by $3$ can be formed using the digits $0,1,2,3,4,7$ and $8$ if each digit is to be used at most once?

The total number of $5$ digit numbers using the digits $0,1,2,3,4,7$ and $8$ is $6\times6\times5\times4\times3=2160.$

Now I found the numbers not divisible by $3$, i.e. even numbers ending in $2,4,8.$

Even numbers from the digits $0,1,2,3,4,7$ and $8$ are $5\times5\times4\times3\times3=930.$

So the numbers divisible by $3$ are $2160-930=1230$ but the answer is $744.$ Where I am wrong?

• $78432,$ $74328$ and $78234$ are divisible by $3.$
– mfl
Jul 21, 2017 at 8:39
• This question is good and should not vote down. Jul 21, 2017 at 8:44

You are wrong in assuming that even numbers can't be divisible by 3. As a counter example, 6 is divisible by 3.

The divisibility rule for 3 states that the if the sum of the digits of the number is divisible by 3, the number itself is divisible 3.

Out of the seven digits given, you need to find groups of 5 for which the sum is divisible by 3. For example, $(1, 2, 3, 4, 8)$ is one such group. For every such group you need to find the number of 5 digit numbers that can be formed and get the total.

• Which is $5!$ for all tuples not containing zero. Jul 21, 2017 at 9:09
• @MichaelHoppe I have a feeling that was left as an exercise for the reader. Jul 21, 2017 at 9:10
• @SwiftsNamesake Indeed Jul 21, 2017 at 9:51

The numbers which are divisible by $3$ are those where the sum of the digits is a multiple of $3$; it doesn't matter what the last digit is. So which sets of $5$ digits are possible? Once you know all of these you can use your method above to say how many numbers contain each set of $5$.

• I got it,the possible numbers are 21084 and its 96 arrangements,21078 and its 96 arrangements,31047 and its 96 arrangements,24078 and its 96 arrangements,12387 and its 120 arrangements,12348 and its 120 arrangements,23478 and its 120 arrangements=744 possibilities Jul 21, 2017 at 9:05
• Yes, that looks good! Jul 21, 2017 at 9:08

Solution

We've to make $$5$$ digit numbers using given $$7$$ digits excluding $$2$$ digits every time. Now,$$0+1+2+3+4+7+8=25$$. As $$25 \pmod 3 \equiv 1$$, duplets to be excluded should have their sum $$\mod 3=1$$. It's not much difficult to find such duplets. Without much trouble, we get :$$(0,1),(0,4),(0,7),(1,3),(2,8),(3,4),(3,7).$$ Thus, there are such $$7$$ duplets & hence $$7$$ such groups of $$5$$ digits.

Now, we find that out of $$7$$ groups, $$4$$ groups have $$0$$ in them which isn't allowed to take 5th place ( otherwise a $$4$$-digit number will be formed.). Total numbers formed by these $$4$$ groups $$=4(5!−4!)=384$$.

Other $$3$$ groups have no zero so total numbers formed by them$$=3(5!)=360$$

Total possibel numbers: $$384+360=744$$

Suppose $$a_1+\cdots+a_n=0\ (\text{mod}\ 3)$$. Then the number $$p:=|\{a_i:a_i=1\}|-|\{a_i:a_i=2\}|$$ is divisible by $$3$$. This is because $$1+2=0\ (\text{mod}\ 3)$$, so after $$1$$s and $$2$$s cancel out, the remaining nonzero numbers must sum to $$0$$ modulo $$3$$. Any nonzero element in $$\mathbb{Z}/3\mathbb{Z}$$ has order $$3$$, so the claim is proved.

Let $$D=\{0,1,2,3,4,7,8\}$$. Modulo $$3$$, the allowed digits $$D$$ becomes $$S:=\{0,1,2,0,1,1,2\}$$ (as a multiset). Now suppose $$n=5$$ and $$a_i\in S$$. Note that $$p\ge 0$$ because the number of $$1$$s in $$S$$ is larger than the number of $$2$$s in $$S$$. Also, $$p\le 3$$ because there are three $$1$$s in $$S$$. Then $$p=3$$ or $$p=0$$.

Suppose $$p=3$$. Then we cannot choose any $$2$$ in $$S$$, so we are forced to choose the remaining $$5$$ digits in $$D$$. There are $$4$$ digits in $$D$$ that can be placed in the first place. All remaining digits can be freely placed in the remaining places. Thus, the number of $$5$$-digit numbers desired when $$p=3$$ is $$4\cdot 4!=96$$.

Suppose $$p=0$$. Then we must choose two $$1$$s and two $$2$$s in $$S$$, or else the number of digits chosen cannot add up to $$5$$. We have $$3$$ choices for the two $$1$$s and $$2$$ choices for the $$0$$. If we choose $$3$$ in $$D$$, then all digits can be placed in all places, so the number of desired numbers when $$p=0$$ and $$3$$ is chosen is $$3\cdot 5!$$. If we choose $$0$$ in $$D$$, then it is similar to the previous paragraph, and the number of desired numbers when $$p=0$$ and $$0$$ is chosen is $$3\cdot 4\cdot 4!$$.

In summary, the answer is $$4\cdot 4!+3\cdot (5!+4\cdot 4!)=744$$.