7
$\begingroup$

I'm solving a problem which asks me to find how many 5-digit numbers with distinct digits are there which are also divisible by $3$. I am familiar that there are $9\cdot9\cdot8\cdot7\cdot6=27216$ five-digit numbers with distinct digits. I know that a natural number $n$ is divisible by $3$ iff the digits sum up to a number divisible by $3$. Now, brute-forcing by a computer algorithm, i found that the result is $20928$. However, I am interested, if there is a mathematical solution for this. I know how to find amount of numbers divisible by $4$ or $5$. We just fix some amount on the last two (or last one) digit. But criterion for divisibility by $3$ is very different from those and I have no idea how to start. Eventually, I would like to find a general formula for $n$-digit numbers.

Edit: Equivallently we want to find how many solution does the equation $a+b+c+d+e=3k$ for $a,b,c,d,e\in\{0,1,2,...,9\}$, $a\neq 0$ also $a,b,c,d,e$ are all distinct and $k\in\mathbb{Z}$ (the highest possible $k$ is in this case $k=11$, the smallest being $k=5$)

Edit (2): According to the ideas from the answer. Make $A=\{0,3,6,9\},B=\{1,4,7\}, C=\{2,5,8\}$. Let's go through the cases that in the number $n$ there are $0,1,2,3,4$ digits from $A$.

i) Suppose none of $A$ is in $n$. We can't form a number divisible by three. We have to take 5 numbers, that is $3$ from $A$ and $2$ from $B$ or $2$ from $A$ and $3$ from $B$. None of the expressions $3(3k+1)+2(3k+2)$ and $2(3k+1)+3(3k+2)$ are divisible by three.

ii) Let $1$ digit from $A$ be in $n$. The amount of ways to choose the digit is $5$. Now we are left to choose $4$ digits. The only possible way is to choose $2$ from $A$ and $2$ from $B$. The amount of ways to do this is ${3\choose 2}^2=9$ which together gives $5\times 9$ ways which can be permuted and alltogether $5\times 9\times 5!=5400$ possible ways.

iii) Let $2$ digits from $A$ be in $n$. The amount of ways to choose the digit is ${5\choose 2}=10$. We are left with $3$ digits. Either all of them are from $A$ or all of them are from $B$. That's $2$ possible ways and all together $20$ possible ways which we permute to obtain $20\times 5!=2400$ possible ways.

iv) Let $3$ digits from $A$ be in $n$. The amount of ways to choose the digits from $A$ is ${5\choose 3}=10$. We are to choose $2$ digits. We must take exactly one from $B$ and exactly one from $C$. The amount of ways to do this is ${3\choose 1}^2=9$. Alltogether $9\times 10$ possible ways which we permute to get $90\cdot5!=10800$ possible ways

v) In the last case where all four digits from $A$ are present, there is no way how to make the number divisible by $3$.

Summing this all up gives $5400+2400+10800=18600$ which is less than what my algorithm yielded. We also have to subtract these which begin with $0$. Can anyone spot the mistake? (If i did any?)

$\endgroup$
  • $\begingroup$ Be careful. Set $A$ has $4$ digits, not $5$. In part (ii), I assume you meant you need to choose two digits from $B$ and two from $C$. In part (ii), I assume you meant need to choose all three digits from $A$ or all three digits from $C$. $\endgroup$ – N. F. Taussig Sep 23 '18 at 14:21
  • $\begingroup$ There is another issue. You are counting four-digit strings rather than four-digit numbers. You have to be careful not to make $0$ the leading digit. $\endgroup$ – N. F. Taussig Sep 23 '18 at 14:27
  • $\begingroup$ Yeah, I will subtract the one leading with $0$ afterwards, thanks for analyzing my work. $\endgroup$ – Michal Dvořák Sep 23 '18 at 15:04
2
$\begingroup$

First calculate four-digit numbers with no zeros that are divisible by 3. These are the five-digit numbers that start wlwith 0.

If there are no digits from $A=\{3,6,9\}$ there must be two each from $B=\{1,4,7\}$ and $C=\{2,5,8\}$ so that the sum is a multiple of $3$. Three ways to pick from $\{1,4,7\}$ and three from $\{2,5,8\}$, or nine in all.
If there is one digit from $\{3,6,9\}$, then you need all of $B$ or all of $C$, six possibilities in all.
I think there are $42$ possibilities altogether, which can each be arranged in $24$ ways, to give $1008$ four-digit multiples of $3$ with no zeroes and no repeated digits.

Do the same thing for five-digit numbers.

$\endgroup$
  • $\begingroup$ I think I got the idea. So the numbers that are equivalent to zero $\mod{3}$ do not interact with the sum (in terms of divisibility by 3) so we go through the cases where there are none 1 of them, 2 of them, 3 of them . But now, I am quite unsure how to treat the zero. Would you please elaborate? $\endgroup$ – Michal Dvořák Sep 23 '18 at 12:29
  • $\begingroup$ $A=\{0,3,6,9\}$ for the five-digit case. $\endgroup$ – Empy2 Sep 23 '18 at 12:37
  • $\begingroup$ Aaah, so you basically take only $\{3,6,9\}$ and make a lemma computing all four digit numbers divisble by three with distinct digit that do NOT contain zero and then subtract the amount from the five digits numbers (even those that begin by zero)? $\endgroup$ – Michal Dvořák Sep 23 '18 at 12:39
  • 1
    $\begingroup$ You want $4\choose k$ rather than $5\choose k$ for $A$. Its moot now, as Christian has a better proof. $\endgroup$ – Empy2 Sep 23 '18 at 14:35
8
$\begingroup$

The set $S$ of five digit numbers with distinct digits has $27\,216$ elements. Write $S=S'\cup S_0$, whereby $S'$ consists of the numbers $n\in S$ without a $0$ in their decimal expansion, and $S_0$ consists of the numbers $n\in S$ with exactly one $0$ in their decimal expansion. I claim that exactly one third of the numbers in $S$, meaning $9072$, are divisible by $3$.

Proof. Consider the following bijective map $f:\>S\to S$: Given a number $n\in S$, apply the map $$1\mapsto2\mapsto3\mapsto4\mapsto5\mapsto6\mapsto7\mapsto8\mapsto9\mapsto1\>, \qquad 0\mapsto0$$ to its digits. Examples: $f(42937)=53148$, $f(31304)=42405$.

The map $f$ is bijective. Furthermore $f$ adds $2$ mod $3$ to numbers in $S'$, and $1$ mod $3$ to numbers in $S_0$. Now both $S'$ and $S_0$ consist of three parts according to the remainder of $n$ modulo $3$, and $f$ permutes the three parts of $S'$ as well as the three parts of $S_0$. It follows that exactly one third of the numbers in $S'$ and one third of the numbers in $S_0$ is divisible by $3$.

$\endgroup$
  • $\begingroup$ Actually, after correcting my work, i got the same number.. 9072. Well, is it a random coincidence that actually 1/3 of them is divisible by 3? By the way, would you please more elaborate why it should follow that one third in $S_0, S'$ is divisible by 3? I couldn't quite get the last sentence in your proof. $\endgroup$ – Michal Dvořák Sep 23 '18 at 15:31
  • $\begingroup$ Just a quick question, so does the bijective map permuting on the congruence classes modulo $n$ imply that all the classes are the same size? (Because that wouldn't be a bijection, right?) Is that correct? $\endgroup$ – Michal Dvořák Sep 23 '18 at 16:06
  • 2
    $\begingroup$ Modulo $3$. – That's my last word on this matter. $\endgroup$ – Christian Blatter Sep 23 '18 at 16:16

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.