## Wednesday, September 27, 2006

### This Is Mental Math?!? Topic: Number Theory. Level: AIME.

Problem: (2006-2007 Warm-Up 2) Let $f(x)$ be the sum of the digits of $x$. Find $f(f(f(8765^{4321})))$.

Solution: Let's try bounding our quantity. We know

$f(x) < 9 \cdot \lceil \log{x} \rceil$

because $\lceil \log{x} \rceil$ is the number of digits of $x$ (except when $x$ is a power of ten, but those are trivial) and the biggest digit is $9$. So we can say that

$f(8765^{4321}) < 9 \cdot \lceil \log{8765^{4321}} \rceil < 9 \cdot \log{10000^{10000}} = 360000$

so

$f(f(8765^{4321})) < 9 \cdot \lceil \log{360000} \rceil < 9 \cdot \log{1000000} = 54$

and

$f(f(f(8765^{4321}))) < 13$

because the largest sum of digits of any number less than $54$ is $4+9 = 13$. So we know our value is less than $13$. But remember that the sum of the digits of a number is equal to itself $\pmod{9}$ (prove this!) and $8765^{4321} \equiv (-1)^{4321} \equiv 8 \pmod{9}$ so our answer is also $8 \pmod{9}$. But the only number less than $13$ that works is then $8$. QED.

--------------------

Comment: Admittedly, this is not likely to show up on a mental math test, but it's feasible to do in your head. The bounding is not horrific and taking the mod is also not bad. Of course, $45$ seconds is pretty quick, but if you knew how to approach the problem already, it was definitely possible (and done).

--------------------

Practice Problem: Show that the sum of the digits of a number is congruent to itself modulo nine.