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 WSMO Accuracy Round Problems/Problem 7"
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
==Problem 7==
+
==Problem==
 
Find the value of <math>\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right),</math> where <math>r_i</math> is the remainder when <math>2^i+3^i</math> is divided by 10.
 
Find the value of <math>\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right),</math> where <math>r_i</math> is the remainder when <math>2^i+3^i</math> is divided by 10.
  
 
==Solution 1==
 
==Solution 1==
 
From Fermat's Little Theorem, we find that <math>a^n\pmod{10}</math> is periodic in cycles of 4. This means that <math>a^n\equiv a^{n+4}\pmod{10}</math> for all <math>a,n.</math> Now, we will compute the first 4 values of <math>2^n+3^n\pmod{10}.</math>
 
From Fermat's Little Theorem, we find that <math>a^n\pmod{10}</math> is periodic in cycles of 4. This means that <math>a^n\equiv a^{n+4}\pmod{10}</math> for all <math>a,n.</math> Now, we will compute the first 4 values of <math>2^n+3^n\pmod{10}.</math>
−
<cmath>\begin{align*}
+
<cmath>
 +
\begin{align*}
 
2^1+3^1\equiv2+3\equiv&\text{ }5\pmod{10}\\
 
2^1+3^1\equiv2+3\equiv&\text{ }5\pmod{10}\\
 
   2^2+3^2\equiv4+9\equiv13\equiv&\text{ }3\pmod{10}\\
 
   2^2+3^2\equiv4+9\equiv13\equiv&\text{ }3\pmod{10}\\
 
2^3+3^3\equiv8+27\equiv35\equiv&\text{ }5\pmod{10}\\
 
2^3+3^3\equiv8+27\equiv35\equiv&\text{ }5\pmod{10}\\
 
2^4+3^4\equiv16+81\equiv97\equiv&\text{ }7\pmod{10}\\
 
2^4+3^4\equiv16+81\equiv97\equiv&\text{ }7\pmod{10}\\
−
\end{align*}</cmath>
+
\end{align*} </cmath>
 
Thus,  
 
Thus,  
−
<math></math>\begin{align*}
+
<cmath>
−
2^n+3^n\equiv&\text{ }5\pmod{10}\tag{for <math>n\equiv1,3\pmod{4}</math>}\\
+
\begin{align*}
−
   2^n+3^n\equiv&\text{ }3\pmod{10}\tag{for <math>n\equiv2\pmod{4}</math>}\\
+
2^n+3^n\equiv&\text{ }5\pmod{10}\tag{for n\equiv1,3\pmod{4}}\\
−
2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for <math>n\equiv0\pmod{4}</math>}\\   
+
   2^n+3^n\equiv&\text{ }3\pmod{10}\tag{for n\equiv2\pmod{4}}\\
−
\end{align*}<cmath>
+
2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for n\equiv0\pmod{4}}\\   
 +
\end{align*} </cmath>
 
This means that  
 
This means that  
−
</cmath>\begin{align*}
+
<cmath>
 +
\begin{align*}
 
\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right)&=\sum_{n=4a,1\leq a\leq25}(20a)+\sum_{n=4a+1,0\leq a\leq24}(20a+5)+\sum_{n=4a+2,0\leq a\leq24}(20a+8)+\sum_{n=4a+3,0\leq a\leq24}(20a+13)\\
 
\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right)&=\sum_{n=4a,1\leq a\leq25}(20a)+\sum_{n=4a+1,0\leq a\leq24}(20a+5)+\sum_{n=4a+2,0\leq a\leq24}(20a+8)+\sum_{n=4a+3,0\leq a\leq24}(20a+13)\\
 
     &=\frac{25\cdot26}{2}\cdot20+\left(\frac{24\cdot25}{2}\cdot20+25\cdot5\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot8\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot13\right)\\
 
     &=\frac{25\cdot26}{2}\cdot20+\left(\frac{24\cdot25}{2}\cdot20+25\cdot5\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot8\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot13\right)\\
Line 24: Line 27:
 
     &=6500+18000+650\\
 
     &=6500+18000+650\\
 
     &=\boxed{25150}\\
 
     &=\boxed{25150}\\
−
\end{align*}<math></math>
+
\end{align*}</cmath>
 
~pinkpig
 
~pinkpig
  

Latest revision as of 10:24, 11 July 2022

Problem

Find the value of $\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right),$ where $r_i$ is the remainder when $2^i+3^i$ is divided by 10.

Solution 1

From Fermat's Little Theorem, we find that $a^n\pmod{10}$ is periodic in cycles of 4. This means that $a^n\equiv a^{n+4}\pmod{10}$ for all $a,n.$ Now, we will compute the first 4 values of $2^n+3^n\pmod{10}.$ \begin{align*} 2^1+3^1\equiv2+3\equiv&\text{ }5\pmod{10}\\ 2^2+3^2\equiv4+9\equiv13\equiv&\text{ }3\pmod{10}\\ 2^3+3^3\equiv8+27\equiv35\equiv&\text{ }5\pmod{10}\\ 2^4+3^4\equiv16+81\equiv97\equiv&\text{ }7\pmod{10}\\ \end{align*} Thus, 

\begin{align*}
	2^n+3^n\equiv&\text{ }5\pmod{10}\tag{for n\equiv1,3\pmod{4}}\\
  	2^n+3^n\equiv&\text{ }3\pmod{10}\tag{for n\equiv2\pmod{4}}\\
	2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for n\equiv0\pmod{4}}\\  
\end{align*} (Error compiling LaTeX. Unknown error_msg)

This means that \begin{align*} \sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right)&=\sum_{n=4a,1\leq a\leq25}(20a)+\sum_{n=4a+1,0\leq a\leq24}(20a+5)+\sum_{n=4a+2,0\leq a\leq24}(20a+8)+\sum_{n=4a+3,0\leq a\leq24}(20a+13)\\ &=\frac{25\cdot26}{2}\cdot20+\left(\frac{24\cdot25}{2}\cdot20+25\cdot5\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot8\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot13\right)\\ &=325\cdot20+300\cdot20\cdot3+25\cdot(5+8+13)\\ &=6500+6000\cdot3+25\cdot26\\ &=6500+18000+650\\ &=\boxed{25150}\\ \end{align*} ~pinkpig

Solution 2

We will begin by examining $2^i\text{ (mod }10\text{)}$ and $3^i\text{ (mod }10\text{)}$:

\[2^1 \equiv 2\text{ (mod }10\text{)}\] \[2^2 \equiv 4\text{ (mod }10\text{)}\] \[2^3 \equiv 8\text{ (mod }10\text{)}\] \[2^4 \equiv 6\text{ (mod }10\text{)}\] \[...\] and \[3^1 \equiv 3\text{ (mod }10\text{)}\] \[3^2 \equiv 9\text{ (mod }10\text{)}\] \[3^3 \equiv 7\text{ (mod }10\text{)}\] \[3^4 \equiv 1\text{ (mod }10\text{)}\] \[...\]

From this, we can note that:

\[r_i = 5 \text{, } i \equiv 1 \text{ (mod }4\text{)}\] \[r_i = 3 \text{, } i \equiv 2 \text{ (mod }4\text{)}\] \[r_i = 5 \text{, } i \equiv 3 \text{ (mod }4\text{)}\] \[r_i = 7 \text{, } i \equiv 0 \text{ (mod }4\text{)}\]

We can simplify our sum as follows:

\[\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right)\] \[=100r_1 + 99r_2 + 98r_3 + ... + r_{100}\] \[=(100+96+...+4)r_1 + (99+95+...+3)r_2 + (98+94+...+2)r_3 + (97+93+...+1)r_4\]


Note that $100+96+...+4 = 4(25+24+...+1) = 4(\frac{25 \cdot 26}{2}) = 1300$:

\[=1300r_1 + (1300-25)r_2 + (1300-50)r_3 + (1300-75)r_4\] \[=5(1300) + 3(1275) + 5(1250) + 7(1225)\] \[=\boxed{25150}\]

~BigKahuna227

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_WSMO_Accuracy_Round_Problems/Problem_7&oldid=175805"