Difference between revisions of "2021 JMPSC Accuracy Problems/Problem 15"

(Solution)
(Solution)
Line 8: Line 8:
  
  
<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{one's}},</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> 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.
+
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 \text{one's}},1</cmath> as desired. <math>\mathbb{Q.E.D.}</math>
  
~pinkpig
+
~pinkpig, <math>\LaTeX</math>/wording fixes by samrocksnature
  
 
==Solution 2 (More Algebraic)==
 
==Solution 2 (More Algebraic)==

Revision as of 16:46, 11 July 2021

Problem

For all positive integers $n,$ define the function $f(n)$ to output $4\underbrace{777 \cdots 7}_{n\ \text{sevens}}5.$ For example, $f(1)=475$, $f(2)=4775$, and $f(3)=47775.$ Find the last three digits of \[\frac{f(1)+f(2)+ \cdots + f(100)}{25}.\]

Solution

We can easily find that $\tfrac{f(1)}{25}=19,\tfrac{f(2)}{25}=191,\tfrac{f(3)}{25}=1911,$ and so on. Thus, we claim$\text{}^*$ that \[\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{n-1 \text{ ones}}.\] 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}.\]



$\text{}^*$ We proceed by induction. Our base case is $\tfrac{f(1)}{25}=\tfrac{475}{25}=19.$ Our inductive assumption is \[\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{n-1 \text{ ones}},\] and we wish to prove that this pattern holds for $f(n+1).$

We can easily find that $f(n+1)=10f(n)+25.$ 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 \text{one's}},1\] as desired. $\mathbb{Q.E.D.}$

~pinkpig, $\LaTeX$/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 )\] We only care about the last $3$ digits, so we evaluate $1+11+111+1111+ \cdots$. Note the expression is simply $1(100)+10(99)+100(98)+1000(97)+ \cdots + 10^{100}$, so factoring a $10$ we have $1(10)+99+10(98)+ \cdots + 10^{99}$. Now, we can divide by $25$ to get \[20+28(1(10)+99+10(98)+100(97) \cdots)+4(444444 \cdots )\] Evaluate the last $3$ digits to get \[20+28(10+99+980+700)+4(444)=\boxed{888} \mod 1000\] $\linebreak$ ~Geometry285