2
$\begingroup$

How many five-digit positive integers are there that are divisible by three?

Given answer is $90000/3=30000$

I know that a number is divisible by $3$ if the sum of its digits are divisible by $3$. I think that for any number $ABCD$, it will be member of either $(0\mod(3))$ or $(1\mod(3))$ or $(2\mod(3))$. I thought that when it belongs to $(0\mod(3))$, we have $4$ choices for the last digits such as $0,3,6,9$. When it belongs to $(1\mod(3))$, we have $3$ choices for the last digits such as $2,5,8$. When it belongs to $(2\mod(3))$, we have $3$ choices for the last digits such as $1,4,7$. Hence, for any $5$ digit numbers, $4/10$ of them will be divisible by $3$. So, the answer is $90000*(4/10)=36000$.

Am I right? If not, can you explain the given answer clearly?

$\endgroup$
4
  • 3
    $\begingroup$ Depending on the lead four digits, there are either $3$ or $4$ ways to fix the units digit to get a multiple of $3$ True, but hard to use. Easier if you fix the least four digits and vary the lead digit. $\endgroup$
    – lulu
    May 2, 2022 at 17:56
  • $\begingroup$ why should i vary over lead digit instead of the last digit ? Is there any way to reach solution using last digit ? $\endgroup$ May 2, 2022 at 17:59
  • $\begingroup$ Because if you vary the lead digit there are $3$ choices no matter what the other four sum to. If you insist on varying the units digit you will have to count the cases for the first four digits, thereby obtaining a (needlessly complicated) recursive solution. $\endgroup$
    – lulu
    May 2, 2022 at 18:01
  • 2
    $\begingroup$ Note: as an unrelated method, note that the least five digit multiple of $3$ is $10002=3\times 3334$ and the greatest is $99999=3\times 33333$. Thus there are $33333-3334+1=30000$ multiples of $3$ in the range. $\endgroup$
    – lulu
    May 2, 2022 at 18:02

5 Answers 5

4
$\begingroup$

You can also look at how many numbers of up to five digits are divisible by $3$ and subtract how many numbers up to four digits are divisible by $3$

The largest five digit number is $99999$, and of the first $99999$ positive integers, $33333$ are divisible by $3$

The largest four digit number is $9999$, and of the first $9999$ positive integers, $3333$ are divisible by $3$

Then the number of five digit numbers divisible by $3$ is just $33333-3333=30000$

$\endgroup$
2
$\begingroup$

Your analysis is close, but overlooks that zero is not permitted in the leftmost digit. The numbers run from $10000$ thru $99999$ inclusive.

Regardless of the sum of the digits $\pmod{3}$ of all but the leftmost digit, there will be exactly $3$ numbers from the set $\{1,2,3,4,5,6,7,8,9\}$ of permissible leftmost digits that cause the overall sum of the digits to be divisible by $(3)$.

Edit
It is also feasible that alternative analysis might lead to a similar (but moderately different) conclusion, with the analysis taking a more in depth look at the sum of the digits from (for example) $10000$ through $19999$ inclusive. However, it obviously couldn't be exactly $(1/3)$ of the numbers, because $(10000)$ is not a multiple of $(3)$.

Edit
I just thought of different analysis that is not that bad. As a number goes from $n$ to $n+1$ to $n+2$ to $n+3$, the congruence class of the number keeps incrementing by $1$.

This assumes clock arithmetic where $1 +$ the congruence class $2 \pmod{3}$ equals the congruence class $0 \pmod{3}$.

So, if you have any set of consecutive numbers, and the congruence class of the first number is equal to $1 +$ the congruence class of the last number, then $(1/3)$ of the numbers will be multiples of $(3)$.

Similarly, if you have any set of consecutive numbers, and the number of elements in this set is a multiple of $(3)$, then exactly $(1/3)$ of the numbers will be multiples of $(3)$.

$\endgroup$
2
  • $\begingroup$ why should i vary over lead digit instead of the last digit ? Is there any way to reach solution using last digit ? $\endgroup$ May 2, 2022 at 17:59
  • $\begingroup$ @Student_000 The problem is that there are $(10)$ possibilities for the rightmost digit. It is feasible that alternative analysis might lead to the same conclusion. However, such alternative analysis would inevitably have to be more complicated than the analysis that I posted at the start of my answer. $\endgroup$ May 2, 2022 at 18:02
2
$\begingroup$

Others have shown how to get the correct answer but nobody seems to have addressed what is wrong with your reasoning

when it belongs to (0mod(3)) ,we have 4 choices for the last digits such as 0,3,6,9

Consider the five digit number 30012. This is clearly (0 mod 3) but ends in the digit 2.

Consider the five digit number 30002. This is clearly (2 mod 3) and also ends in the digit 2.

30022 is (1 mod 3) and also ends in the digit 2.

The last digit is not related to giving any particular remainder when divided by 3.

$\endgroup$
1
  • 1
    $\begingroup$ I think you've misunderstood the sentence that you quote. As I understand it, the "it" refers to the first four digits interpreted as an integer; so in your example of 30012, that would be 3001, which is congruent to 1 (mod 3), not to 0 (mod 3). $\endgroup$
    – ruakh
    May 3, 2022 at 5:06
1
$\begingroup$

If I asked you a simpler question, like how many numbers betwen $1$ and $9$ are divisible by $3$, would you answer it combinatorially? Maybe you might just list all the numbers and cross out all those which aren't multiples of $3$. But thinking just a little bit more would give you an improved method: find the first and last numbers in that range that are multiples of $3$ (namely, $3$ and $9$ respectively) then list only the multiples of $3$ in that range, giving you $3,6,9$ and a quicker route to an answer. But think just a bit deeper and you'll hit upon the final improvement, just take the first and last numbers that are multiples of $3$ and figure out their place in the three times table. Basically divide them by $3$. So you get $3 = 1\times 3$ and $9 = 3\times 3$ and you can now reduce the problem to finding out how many consecutive numbers lie between $1$ and $3$ inclusive. This is trivial, it's just $3 - 1 + 1 = 3$ (subtract the minimum from the maximum and add one to make sure the initial value is counted).

Working analogously in the actual problem, you find the first in the range that is divisible by $3$, and that's $10002$ (quite easy to figure out using the divisibility rule for $3$, which is that the sum of the digits must also be divisible by $3$). Then figure out the last (which is just the highest $5$ digit number, $99999$ since $9$ is a multiple of $3$ and repeating it will still give a digit sum that's a multiple of $3$). $10002 = 3334 \times 3$ while $99999 = 33333 \times 3$,giving you the answer of $33333 - 3334 + 1 = 33333 - 3333 = 30000$, just as the answer key stated.

The reason why your method fails is that you're only considering the last digits, whereas all the digits matter when you're thinking about divisibility by $3$, since we need to consider the digit sum. Considering only the last digit would work in problems where you're considering divisibility by $2$ or $5$ or $10$.

$\endgroup$
1
$\begingroup$

Other answers have explained how you can derive the correct answer; I will attempt to address the mistake in your reasoning.

This part of what you wrote is correct:

I know that a number is divisible by $3$ if sum of its digits are divisible by $3$.I think that for any number $ABCD$ , it will be member of either $(0\mod(3))$ or $(1\mod(3))$ or $(2\mod(3))$.I though that when it belongs to $(0\mod(3))$ ,we have $4$ choices for the last digits such as $0,3,6,9$ .when it belongs to $(1\mod(3))$ ,we have $3$ choices for the last digits such as $2,5,8$ . when it belongs to $(2\mod(3))$ ,we have $3$ choices for the last digits such as $1,4,7$ .

But this part is not:

Hence ,for any $5$ digits numbers , $4/10$ of them will be divisible by $3$.$

This doesn't at all follow from what you wrote above; what you wrote above involves $4$ and $10$, but not in such a way that it makes sense to divide them.

As it happens, there are 3000 four-digit numbers $ABCD$ that are $\equiv 0 \pmod 3$, there are 3000 four-digit numbers $ABCD$ that are $\equiv 1 \pmod 3$, and there are 3000 four-digit numbers $ABCD$ that are $\equiv 2 \pmod 3$. Combining this with what you wrote above, we have that there are $3000 \times 4 + 3000 \times 3 + 3000 \times 3 = 30000$ five-digit numbers $ABCDE$ that are $\equiv 0 \pmod 3$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .