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