Total number of 8 digit numbers divisible by 3 and composed of 4, 5 and 6? I know that the total possible 8 digit numbers made using 4, 5 and 6 is $3^8$. But if one more constraint is added like the number must be divisible by 3, how do we find it. The answer is $3^7$, but I cannot explain it. I am having hard time with counting. Any help is appreciated.
 A: For any integer $a$, exactly one of $a+4$, $a+5$, and $a+6$ will be divisible by 3.
Thus, whenever you have chosen the first 7 digits, exactly one of the choices for the last digit will result in a number that's divisible by 3.
A: We prove by induction that $\frac{1}{3}$ of the $n$-digit numbers have remainder $0$ on division by $3$, $\frac{1}{3}$ have remainder $1$, and $\frac{1}{3}$ have remainder $2$.  It is useful to use the language of probabilities: we prove that a randomly selected number of length $n$ has probability $\frac{1}{3}$ of having remainder $0$, of having remainder $1$, and of having remainder $2$.
Suppose the result is correct when $n=k$. We show the result is true for $n=k+1$.
Recall that the remainder of a number on division by $3$ is the remainder when the sum of its digits is divided by $3$. 
Take a $(k+1)$-digit number. It is equally likely to end in $4$, $5$, or $6$. If it ends in $4$, then it has remainder $0$ precisely if the number obtained by deleting the $4$ has remainder $2$. The probability of this is, by the induction hypothesis, $\frac{1}{3}$. A similar calculation shows the probability is also $\frac{1}{3}$ if the last digit is $5$, and if the last digit is $6$. 
Similar calculations show that the same is true for remainder $1$ and for remainder $2$.
