2021 JMPSC Accuracy Problems/Problem 15

Problem

For all positive integers define the function to output For example, , , and Find the last three digits of

Solution

We can easily find that Thus, we claim that Now, we find we can easily find that $$ (Error compiling LaTeX. Unknown error_msg)\left(\frac{f(1)+f(2)+ \cdots + f(100)}{25}\right)\equiv(19+191+911+(111)(97))\equiv 11888 \pmod{1000} \rightarrow \boxed{888}.$$ (Error compiling LaTeX. Unknown error_msg)\text{}^*\frac{f(1)}{25}=\frac{475}{25}=19=19\underbrace{111 \cdots 1}_{(1-1=0)\text{one's}}1\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{(n-1)\text{one's}}1.f(n+1)=10f(n)+25.\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{(n-1)\text{one's}}1,$$ (Error compiling LaTeX. Unknown error_msg)\frac{f(n+1)}{25}=10(19\underbrace{111 \cdots 1}_{(n-1)\text{one's}}1)+1=19\underbrace{111 \cdots 1}_{(n)\text{one's}}1$ as desired.

~pinkpig

Solution 2 (More Algebraic)

We only care about the last digits, so we evaluate . Note the expression is simply , so factoring a we have . Now, we can divide by to get Evaluate the last digits to get ~Geometry285