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 16:38, 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 $$ (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