Difference between revisions of "2021 JMPSC Accuracy Problems/Problem 15"
(→Solution) |
(→Solution) |
||
| Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
| − | 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) | + | 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></math>\left(\frac{f(1)+f(2)+ \cdots + f(100)}{25}\right)\equiv(19+191+911+(111)(97))\equiv 11888 \pmod{1000} \rightarrow \boxed{888}.<math> |
| − | <math>\text{}^*< | + | </math>\text{}^*<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< | + | 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.< | + | 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$ as desired. |
~pinkpig | ~pinkpig | ||
Revision as of 15:38, 11 July 2021
Problem
For all positive integers 
define the function 
to output 
For example, 
, 
, and 
Find the last three digits of ![\[\frac{f(1)+f(2)+ \cdots + f(100)}{25}.\]](http://latex.artofproblemsolving.com/2/4/4/244944bb29f9d9d942d159a2b7178e3b06f5728a.png)
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)
![\[\sum_{n=1}^{100} f(n) = 5(100)+70(\underbrace{1+11+111+1111+ \cdots}_{\text{100 1s}}) + 100(44444 \cdots )\]](http://latex.artofproblemsolving.com/9/e/2/9e21c3914f4d18b4548d6668bc71d345f7f102e9.png)
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 ![\[20+28(1(10)+99+10(98)+100(97) \cdots)+4(444444 \cdots )\]](http://latex.artofproblemsolving.com/a/8/a/a8a8c8b9f1ef583e93627cd4a496bd0c1d97c6d1.png)
Evaluate the last digits to get ![\[20+28(10+99+980+700)+4(444)=\boxed{888} \mod 1000\]](http://latex.artofproblemsolving.com/b/9/9/b99a415893ad3f1d40e543fd280678195702586e.png)
~Geometry285
