Difference between revisions of "2021 JMPSC Accuracy Problems/Problem 15"
(→Solution) |
(→Solution) |
||
| Line 10: | Line 10: | ||
<math>\text{}^*</math> We proceed by induction. Our base case is <math>\tfrac{f(1)}{25}=\tfrac{475}{25}=19.</math> Our inductive assumption is <cmath>\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{n-1 \text{ ones}},</cmath> and we wish to prove that this pattern holds for <math>f(n+1).</math> | <math>\text{}^*</math> We proceed by induction. Our base case is <math>\tfrac{f(1)}{25}=\tfrac{475}{25}=19.</math> Our inductive assumption is <cmath>\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{n-1 \text{ ones}},</cmath> and we wish to prove that this pattern holds for <math>f(n+1).</math> | ||
| − | We can easily find that <math>f(n+1)=10f(n)+25.</math> Using our inductive assumption, we obtain <cmath>\frac{f(n+1)}{25}=10 \cdot (19\underbrace{111 \cdots 1}_{n-1 \text{ones}})+1=19 \cdot \underbrace{111 \cdots 1}_{n-1 \text{ ones}},</cmath> as desired. <math>\mathbb{Q.E.D.}</math> | + | We can easily find that <math>f(n+1)=10f(n)+25.</math> Using our inductive assumption, we obtain <cmath>\frac{f(n+1)}{25}=10 \cdot (19\underbrace{111 \cdots 1}_{n-1 \text{ ones}})+1=19 \cdot \underbrace{111 \cdots 1}_{n-1 \text{ ones}},</cmath> as desired. <math>\mathbb{Q.E.D.}</math> |
~pinkpig, <math>\LaTeX</math>/wording fixes by samrocksnature | ~pinkpig, <math>\LaTeX</math>/wording fixes by samrocksnature | ||
Revision as of 15:47, 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 
and so on. Thus, we claim
that ![\[\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{n-1 \text{ ones}}.\]](http://latex.artofproblemsolving.com/1/1/2/1125b7655524129590316988ce94b953d81ad98f.png)
Now, we find we can easily find that ![\[\frac{f(1)+f(2)+ \cdots + f(100)}{25}\equiv19+191+911+111 \cdot 97 \equiv 11888 \pmod{1000} \rightarrow \boxed{888}.\]](http://latex.artofproblemsolving.com/a/b/9/ab9b217f16f08c97c8609d88c930bbb5d9084ea7.png)
We proceed by induction. Our base case is 
Our inductive assumption is ![\[\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{n-1 \text{ ones}},\]](http://latex.artofproblemsolving.com/4/0/1/4012b2fb744a7b11be5583f847fd34067bf310a9.png)
and we wish to prove that this pattern holds for 
We can easily find that 
Using our inductive assumption, we obtain ![\[\frac{f(n+1)}{25}=10 \cdot (19\underbrace{111 \cdots 1}_{n-1 \text{ ones}})+1=19 \cdot \underbrace{111 \cdots 1}_{n-1 \text{ ones}},\]](http://latex.artofproblemsolving.com/6/8/0/6806dbb4bb53f83f52bdca01b3969e1feaf7d2e6.png)
as desired. 
~pinkpig, 
/wording fixes by samrocksnature
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
