2021 WSMO Accuracy Round Problems/Problem 7

Problem 7

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

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

Page

Toolbox

Search

2021 WSMO Accuracy Round Problems/Problem 7

Problem 7

Solution