2022 AMC 10B Problem 25

Below is the professionally curated solution for Problem 25 of the 2022 AMC 10B, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2022 AMC 10B solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:modular arithmeticnumber basepower of 2

Difficulty rating: 2390

25.

Let x0,x1,x2,x_0,x_1,x_2,\dotsc be a sequence of numbers, where each xkx_k is either 00 or 1.1. For each positive integer n,n, define Sn=k=0n1xk2kS_n = \sum_{k=0}^{n-1} x_k 2^k Suppose 7Sn1(mod2n)7S_n \equiv 1 \pmod{2^n} for all n1.n \geq 1. What is the value of the sum x2019+2x2020+x_{2019} + 2x_{2020} + 4x2021+8x2022?4x_{2021} + 8x_{2022}?

6 6

7 7

12 12

14 14

15 15

Solution:

Note first that S2023S201922019=x2019+\dfrac{ S_{2023} - S_{2019}}{2^{2019}} = x_{2019} +2x2020+4x2021+8x2022. 2x_{2020} + 4x_{2021} + 8x_{2022}. Therefore, we should attempt to find S2019,S2023.S_{2019}, S_{2023}. Also, note that 0Snk=0n12k<2n.0 \leq S_n \leq \sum_{k=0}^{n-1} 2^k < 2^n.

Now, since 7Sn1(mod2n),7S_n \equiv 1 \pmod{2^n}, we know 7Sn=m2n+1    7S_n = m2^n +1 \impliesSn=m2n+17 S_n = \dfrac {m2^n+1}{7} for some integer m.m. Also, since 0Sn<2n,0 \leq S_n < 2^n, we know 0m2n+17<2n.0 \leq \dfrac {m2^n+1}7 < 2^n. This means 0m<7.0 \leq m < 7. Now, we find mm such that m2n+1m2^n + 1 is divisible by 7.7. This makes m2n+10mod7.m2^n + 1 \equiv 0 \mod 7.

If n=2019,n=2019, then 0m22019+10 \equiv m2^{2019} + 1 \equiv m(23)673+1 m(2^3)^{673}+1 \equiv m8673+1m+1, m8^{673} + 1\equiv m+1, so m=6.m=6. This makes S2019=6(22019)+17.S_{2019} = \dfrac {6(2^{2019})+1}{7}.

If n=2023,n=2023, then 0m22023+10 \equiv m2^{2023} + 1 m(23)6742+1 \equiv m(2^3)^{674}\cdot 2+1 m86742+1 \equiv m8^{674}\cdot 2 + 12m+1,\equiv 2m+1, so m=3.m=3. This makes S2023=3(22023)+17.S_{2023} = \dfrac {3(2^{2023})+1}{7}.

Our answer is S2023S201922019=122019(322023+17622019+17)=4222019722019=6.\frac{S_{2023}-S_{2019}}{2^{2019}}=\frac{1}{2^{2019}}\left(\frac{3\cdot2^{2023}+1}{7}-\frac{6\cdot2^{2019}+1}{7}\right)=\frac{42\cdot2^{2019}}{7\cdot2^{2019}}=6.

Thus, the correct answer is A .

Problem 25 in Other Years