Difference between revisions of "2021 JMPSC Accuracy Problems/Problem 15"
(→Solution) |
(→Solution) |
||
Line 8: | Line 8: | ||
− | <math>\text{}^*</math> | + | <math>\text{}^*</math> We proceed by induction. Our base case is <math>\tfrac{f(1)}{25}=\tfrac{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. | 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. | ||
Revision as of 16:41, 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 and so on. Thus, we claim
that
Now, we find we can easily find that
We proceed by induction. Our base case is
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