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)
 
(14 intermediate revisions by 2 users not shown)
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 <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>
+
We can easily find that <math>\tfrac{f(1)}{25}=19,\tfrac{f(2)}{25}=191,\tfrac{f(3)}{25}=1911,</math> and so on. Thus, we claim<math>\text{}^*</math> that <cmath>\frac{f(n)}{25}=19\underbrace{111 \cdots 1}_{n-1 \text{ ones}}.</cmath> Now, we find we can easily find that <cmath>\frac{f(1)+f(2)+ \cdots + f(100)}{25}\equiv19+191+911+111 \cdot 97 \equiv 11888 \pmod{1000} \rightarrow \boxed{888}.</cmath>
  
  
  
  
−
<math>\text{}^*</math> This will be a proof by induction.  
+
<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>
−
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</math> as desired.
 
  
−
~pinkpig
+
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>
 +
 
 +
~Solution by pinkpig, <math>\LaTeX</math>/wording fixes by samrocksnature
  
 
==Solution 2 (More Algebraic)==
 
==Solution 2 (More Algebraic)==
Line 18: Line 18:
 
<math>\linebreak</math>
 
<math>\linebreak</math>
 
~Geometry285
 
~Geometry285
 +
 +
 +
 +
==See also==
 +
#[[2021 JMPSC Accuracy Problems|Other 2021 JMPSC Accuracy Problems]]
 +
#[[2021 JMPSC Accuracy Answer Key|2021 JMPSC Accuracy Answer Key]]
 +
#[[JMPSC Problems and Solutions|All JMPSC Problems and Solutions]]
 +
{{JMPSC Notice}}

Latest revision as of 00:19, 12 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-1 \text{ ones}},\] as desired. $\mathbb{Q.E.D.}$

~Solution by 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


See also

  1. Other 2021 JMPSC Accuracy Problems
  2. 2021 JMPSC Accuracy Answer Key
  3. All JMPSC Problems and Solutions

The problems on this page are copyrighted by the Junior Mathematicians' Problem Solving Competition. JMPSC.png

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