Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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></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>
+
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 <cmath>\left(\frac{f(1)+f(2)+ \cdots + f(100)}{25}\right)\equiv(19+191+911+(111)(97))\equiv 11888 \pmod{1000} \rightarrow \boxed{888}.</cmath>
  
  
  
  
−
</math>\text{}^*<math> This will be a proof by induction.  
+
<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<math>
+
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.<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.
+
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.
  
 
~pinkpig
 
~pinkpig

Revision as of 15:38, 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}=\tfrac{475}{25}=19,\tfrac{4775}{25}=191,\tfrac{47775}{25}=1911.$ Thus, we claim$\text{}^*$ that $\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{(n-1)\text{one's}}1.$ Now, we find we can easily find that \[\left(\frac{f(1)+f(2)+ \cdots + f(100)}{25}\right)\equiv(19+191+911+(111)(97))\equiv 11888 \pmod{1000} \rightarrow \boxed{888}.\]



$\text{}^*$ This will be a proof by induction. Base Case: $\frac{f(1)}{25}=\frac{475}{25}=19=19\underbrace{111 \cdots 1}_{(1-1=0)\text{one's}}1$ I claim that $\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{(n-1)\text{one's}}1.$ We can easily find that $f(n+1)=10f(n)+25.$ Thus, since $\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{(n-1)\text{one's}}1,$ $\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 )\] 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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_JMPSC_Accuracy_Problems/Problem_15&oldid=158001"