1
$\begingroup$

Find number of seven digit numbers divisible by $3$ with

$1.$ Repetition

$2.$ Without Repetition

For Part $1.$ The least seven digit number divisible by $3$ is $1000002$ and highest seven digit number is $9999999$

So total is $3000000$

For Part $2$ The least such number is $1023456$ and the next is $1023459$

Now sum of the digits of $1023456$ is $21$.

So if we include $7$ by removing one of the digits in $1023456$ then the digits that can be removed is $1$ or $4$.

If we include $8$ then digits that can be removed is $2$ or $5$.

but we get more cases here, any better way to approach?

$\endgroup$
  • $\begingroup$ yes i missed that $\endgroup$ – Ekaveera Kumar Sharma Dec 2 '17 at 16:49
  • $\begingroup$ Is it of any help to see first which digits will be omitted? There are only 84 such sets, and I bet about a third is right. Then take permutations of those. Then see how many of them begin with 0? $\endgroup$ – user491874 Dec 2 '17 at 16:58
  • $\begingroup$ Via a program i have that the answer is $190080$ $\endgroup$ – John Lou Dec 2 '17 at 17:00
2
$\begingroup$

Let $N_7 = \text{what you are looking for}$

However, this consists of one set that doesn't use any zeros - $(NZ)_7$ - and another that does. The number in the set that uses zeros can be defined recursively as $6(NZ)_6$ because the zero can be placed in 6 different places.

Notice that $(NZ)_7 = \frac{\text{pair of two numbers that are divisible by 3}}{9c2} \cdot(9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3)$

This is because the total sum of $1,2, ..8, 9$ is $45$ and we need to remove two numbers such that the sum of the others is still a multiple fo $3$ ie the two numbers we remove must be a multiple of $3$

Therefore, $(NZ)_7 = \frac{(NZ)_2}{9P2}(9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3)$

Similarly, $(NZ)_6 = \frac{(NZ)_3}{9P3}(9\cdot8\cdot7\cdot6\cdot5\cdot4)$

$(NZ)_2$ can be counted, but also it can be expressed as $9\cdot3 - \frac{1}{9}\cdot 9 \cdot 3$. This is found because if the first is $0 \mod 3$, then there is an overcounting (1/3 of such cases are false $1/3 *1/3 = 1/9$)

Similarly, $(NZ)_2=9\cdot 8 \cdot 3 - \frac{2}{8} \cdot \frac{2}{3} \cdot 9 \cdot 8\cdot 3$. Here, the second part is found by considering the probability that the second number chosen is the same modulus as the first ( $2/8$), which results in only $1/3$ of the possible last digits (so we subtract out $2/3$)

Therefore,

$$N_7 = \frac{9 \cdot 3 - 3}{72}(9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3) + 6 \cdot \frac{9\cdot8\cdot3-4\cdot9}{504}(9\cdot8\cdot7\cdot6\cdot5\cdot4) = 190080$$

This is definitely not my most eloquent answer, so please ask me questions if something is confusing, and I'll try to explain my thought process.

$\endgroup$
1
$\begingroup$

$(1)$ Number of possible digit combinations without $0$ digit: $\binom{9}{7}=36 $

$(2)$ Number of possible digit combinations including $0$ digit: $\binom{9}{6}=84 $

So there are $36 \cdot 7!+84 \cdot 6 \cdot 6!=544320$ numbers without digit repetition.

Now we have to find the numbers divisible by $3$.

We can seperate the cases:

$(1.a)$ $1$ digit divisible by $3$, $6$ digits not divisible by $3$: $\binom{3}{1}\binom{6}{6}=3\cdot1=3$

Out of the $\binom{6}{6}=1$ case $$(1,2,4,5,7,8)$$ $1$ is divisible by $3$, so there are $\binom{3}{1}\cdot 1=3$ numbers divisible by $3$.

$(1.b)$ $2$ digits divisible by $3$, $5$ digits not divisible by $3$: $\binom{3}{2}\binom{6}{5}=3\cdot6=18$

Out of the $\binom{6}{5}=6$ cases $$(1,2,4,5,7),(1,2,4,5,8),(1,2,4,7,8),(1,2,5,7,8),(1,4,5,7,8),(2,4,5,7,8)$$ $0$ is divisible by $3$, so there are $\binom{3}{2}\cdot 0=0$ numbers divisible by $3$.

$(1.c)$ $3$ digits divisible by $3$, $4$ digits not divisible by $3$: $\binom{3}{3}\binom{6}{4}=1\cdot15=15$

Out of the $\binom{6}{4}=15$ cases $$(1,2,4,5),...,(4,5,7,8)$$ $9$ is divisible by $3$, so there are $\binom{3}{3}\cdot 9=9$ numbers divisible by $3$.

So in the $(1)$ case there are $(3+0+9)\cdot 7!=12\cdot 7!=60480$ numbers divisible by $3$.

Similarly we can find that in the $(2)$ case there are $=30\cdot 6\cdot 6!=129600$ numbers divisible by $3$.

Maybe it's not the best approach and for some numbers we have to test the 3-divisibility, but we got the answer: $60480+129600=190080$

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