Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many numbers smaller than $2.10^8$ and divisible by $3$ can be written by means of the digits $0$,$1$ and $2$? Left Zero padding not allowed.

I am getting this as - 3 digits - 2*3 = 6 4 digits - 2*3*3 = 18 5 digits - 2*3*3*3 = 54 6 digits - 2*3*3*3*3 = 162 7 digits - 2*3*3*3*3*3*3 = 486 8 digits - 2*3*3*3*3*3*3*3 = 1458 From 1*10^8 to 2*10^8 - 2*3*3*3*3*3*3*3*3/2 = 2187

I get 4371 as the answer, but in book this show 4351, am I making an Error somewhere. Please help!! Thanks.

share|improve this question
    
What is meant by zero padding? Padding on left, right, or even in between the other digits? –  Milind May 6 '13 at 4:31
    
Zeros on left... Not allowed. –  Joy May 6 '13 at 4:37
    
Total number of numbers divisible by $3$ is $2.10^8/3$. Now we need to count only the numbers whose digit are $0,1,2 $ –  Learner May 6 '13 at 5:04

1 Answer 1

We solve the simpler problem of counting the numbers from $0$ to $10^8-1$ of the right shape that are divisible by $3$. We do allow zero padding to make all the numbers into $8$-digit numbers. This makes no difference to the count.

The same method works for the other half of our interval.

We use a general approach, though the particular case is too simple and quickly collapses. One could then in hindsight give a slicker argument, but we won't do that.

Let $a(n)$ be the number of $n$-digit numbers that use only $0$, $1$, and $2$ and are divisible by $3$. Let $b(n)$ be the number of $n$-digit numbers, of the right form, that give remainder $1$ on division by $3$, and let $c(n)$ be the same thing, except for remainder $2$. We have $a(1)=b(1)=c(1)=1$. Note that $$a(n+1)=a(n)+b(n)+c(n).$$ This is because a qualifying $n+1$ digit number can be obtained by appending a $0$ to an $n$-digit number divisible by $3$, or a $2$ to an $n$-digit number that has remainder $1$, or a $1$ to an $n$-digit number that has remainder $2$. Similarly, we have $b(n)=a(n)+b(n)+c(n)$ and $c(n)=a(n)+b(n)+c(n)$.

It follows that $a(2)=b(2)=c(2)=3$, and $a(3)=b(3)=c(3)=9$, and so on. Thus $a(8)=3^7$.

For the numbers from $1\times 10^8$ to $2\times 10^8-1$, do the same calculation for numbers of the form $1x$, where $x$ is a (padded) $8$-digit number.

share|improve this answer
    
I am getting this as - 3 digits - 2*3 = 6 4 digits - 2*3*3 = 18 5 digits - 2*3*3*3 = 54 6 digits - 2*3*3*3*3 = 162 7 digits - 2*3*3*3*3*3*3 = 486 8 digits - 2*3*3*3*3*3*3*3 = 1458 From 1*10^8 to 2*10^8 - 2*3*3*3*3*3*3*3*3/2 = 2187 I get 4371 as the answer, but in book this show 4351, am I making an Error somewhere. Please help!! Thanks. –  Joy May 6 '13 at 7:31
    
Will get back to you, probably not for half day or so, sleep, then busy half-day. –  André Nicolas May 6 '13 at 9:05
1  
Checked again. from $0$ to $2\times 10^8$, have $2\times 3^7$. Take away $1$ if we don't want to count $0$. Your counts are correct, bur left out the $2$ digit $12$ and $21$, and (subject to interpretation) the $1$-digit number $0$. So $4373$ or $4374$, depending on interpretation. I do not see anything that we can discard that would lead to $4351$. –  André Nicolas May 6 '13 at 21:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.