Difference between revisions of "2021 JMPSC Accuracy Problems/Problem 15"
(→Solution) |
(→Solution) |
||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | We can easily find that <math>\ | + | We can easily find that <math>\tfrac{f(1)}{25}=\tfrac{475}{25}=19,\tfrac{4775}{25}=191,\tfrac{47775}{25}=1911.</math> Thus, we claim<math>\text{}^*</math> that <math>\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{(n-1)\text{one's}}1.</math> Now, we find we can easily find that <math>\left(\frac{f(1)+f(2)+ \cdots + f(100)}{25}\right)\pmod{1000}\equiv(19+191+911+(111)(97))\pmod{1000}\equiv 11888 \pmod{1000}=\boxed{888}.</math> |
Revision as of 16:37, 11 July 2021
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
This will be a proof by induction.
Base Case:
I claim that
We can easily find that
Thus, since
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