**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.

I totally guessed that you would write the problem so that it would turn out to be the remainder mod 9. Although I found that remainder in a much slower process than I could have.

ReplyDelete8765 = 9000 - 270 + 27 + 8

Lol. That'd be pretty cruel if it wasn't just the remainder.

ReplyDeleteHAPPY BIRTHDAY!

ReplyDelete