A nonnegative integer $m$ is called a “six-composited number” if $m$ and the sum of its digits are both multiples of $6$. How many “six-composited numbers” that are less than $2012$ are there?
Problem
Source: China south east mathematical olympiad 2012 day2 problem 5
Tags: modular arithmetic, number theory unsolved, number theory
professordad
17.07.2013 18:55
Note that if $m$ is divisible by 3, the sum of its digits is divisible by 3. So the only conditions for $m$ (besides being a nonnegative integer) are that its last digit is even, and the sum of all its digits is divisible by 6.
$0$ and $6$ are the only one digit numbers that work.
For two digit numbers, letting $m = 10a + b$ we see that $a + b \equiv 0 \pmod{6}$, and $b$ is even. If b=2 or 8, a can only be 4; if b=4, a can be 2 or 8; if b=0 or 6, a can only be 6, so there are $5$ two digit numbers that work.
For three digit numbers, letting $m = 100a + 10b + c$ we see that $a + b + c \equiv 0 \pmod{6}$, and $c$ is even. If c=2 or 8, $a+b$ can only be 4; there are 4 ways for $a+b$ to equal 4. If c=4, $a+b$ can be 2 or 8; $a+b=2$ has 2 solutions, and $a+b=8$ has 8 solutions. If c=0 or 6, $a+b$ can only be 6; this has 6 solutions. So in total we have $8+10+12=30$ solutions here.
For four digit numbers, let the thousands digit be 1; then $m = 1000 + 100b + 10c + d$. We know $b + c + d \equiv 5 \pmod{6}$, and $d$ is even. If d=2 or 8, $b+c$ can be 3 or 9; there are 4 and 10 solutions respectively. If d=4, $b+c$ can be 1 or 7; there are 2 and 8 solutions respectively. If d=0 or 6, $b+c$ can only be 5; this has 6 solutions. So in total we have $28+10+12=50$ solutions here.
For four digit numbers with thousands digit 2, the only solutions are 2004 and 2010.
The answer should be $2+5+30+50+2=\boxed{89}$.