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

2022 AMC 10B Problems/Problem 25

Revision as of 08:16, 5 December 2022 by MRENTHUSIASM (talk | contribs)
The following problem is from both the 2022 AMC 10B #25 and 2022 AMC 12B #23, so both problems redirect to this page.

Problem

Let $x_0,x_1,x_2,\dotsc$ be a sequence of numbers, where each $x_k$ is either $0$ or $1$. For each positive integer $n$, define \[S_n = \sum_{k=0}^{n-1} x_k 2^k\]

Suppose $7S_n \equiv 1 \pmod{2^n}$ for all $n \geqslant 1$. What is the value of the sum \[x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}\]

$\textbf{(A) } 6 \qquad \textbf{(B) } 7 \qquad \textbf{(C) }12\qquad \textbf{(D) } 14\qquad \textbf{(E) }15$

Solution 1

In binary numbers, we have \[S_n = (x_{n-1} x_{n-2} x_{n-3} x_{n-4} \ldots x_{2} x_{1} x_{0})_2.\] It follows that \[8S_n = (x_{n-1} x_{n-2} x_{n-3} x_{n-4} \ldots x_{2} x_{1} x_{0}000)_2.\] We obtain $7S_n$ by subtracting the equations: \[\begin{array}{cccccccccccc} & x_{n-1} & x_{n-2} & x_{n-3} & x_{n-4} & \ldots & x_2 & x_1 & x_0 & 0 & 0 & 0 \\ -\quad & & & & x_{n-1} & \ldots & x_5 & x_4 & x_3 & x_1 & x_1 & x_0 \\ \hline & & & & & & & & & & & \\ [-2.5ex] & & & & 0 & \ldots & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array}\]

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

~MRENTHUSIASM

Solution 2

First, notice that \[x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022} = \frac{S_{2023} - S_{2019}}{2^{2019}}.\] Then since $S_n$ is the modular inverse of $7$ in $\mathbb{Z}_{2^n}$, we can perform the Euclidean Algorithm to find it for $n = 2019,2023$.

Starting with $2019$, \begin{align*} 7S_{2019} &\equiv 1 \pmod{2^{2019}} \\ 7S_{2019} &= 2^{2019}k + 1. \end{align*} Now, take both sides $\operatorname{mod} \ 7$: \[0 \equiv 2^{2019}k + 1 \pmod{7}.\] Using Fermat's Little Theorem, \[2^{2019} = (2^{336})^6 \cdot 2^3 \equiv 2^3 \equiv 1 \pmod{7}.\] Thus, \[0 \equiv k + 1 \pmod{7} \implies k \equiv 6 \pmod{7} \implies k = 7j + 6.\] Therefore, \[7S_{2019} = 2^{2019} (7j + 6) + 1 \implies S_{2019} = \frac{2^{2019} (7j + 6) + 1}{7}.\]

We may repeat this same calculation with $S_{2023}$ to yield \[S_{2023} = \frac{2^{2023} (7h + 3) + 1}{7}.\] Now, we notice that $S_n$ is basically an integer expressed in binary form with $n$ bits. This gives rise to a simple inequality, \[0 \leqslant S_n \leqslant 2^n.\] Since the maximum possible number that can be generated with $n$ bits is \[\underbrace{{11111\dotsc1}_2}_{n} = \sum_{k=0}^{n-1} 2^k = 2^n - 1 \leqslant 2^n.\] Looking at our calculations for $S_{2019}$ and $S_{2023}$, we see that the only valid integers that satisfy that constraint are $j = h = 0$. \[\frac{S_{2023} - S_{2019}}{2^{2019}} = \frac{\tfrac{2^{2023} \cdot 3 + 1}{7} - \tfrac{2^{2019} \cdot 6 + 1}{7}}{2^{2019}} = \frac{2^4 \cdot 3 - 6}{7} = \boxed{\textbf{(A) } 6}.\] ~ $\color{magenta} zoomanTV$

Solution 3

As in Solution 2, we note that \[x_{2019}+2x_{2020}+4x_{2021}+8x_{2022}=\frac{S_{2023}-S_{2019}}{2^{2019}}.\] We also know that $7S_{2023} \equiv 1 \pmod{2^{2023}}$ and $7S_{2019} \equiv 1 \pmod{2^{2019}}$, this implies: \[\textbf{(1) } 7S_{2023}=2^{2023}\cdot{x} + 1,\] \[\textbf{(2) } 7S_{2019}=2^{2019}\cdot{y} + 1.\] Dividing by $7$, we can isolate the previous sums: \[\textbf{(3) } S_{2023}=\frac{2^{2023}\cdot{x} + 1}{7},\] \[\textbf{(4) } S_{2019}=\frac{2^{2019}\cdot{y} + 1}{7}.\] The maximum value of $S_n$ occurs when every $x_i$ is equal to $1$. Even when this happens, the value of $S_n$ is less than $2^n$. Therefore, we can construct the following inequalities: \[\textbf{(3) } S_{2023}=\frac{2^{2023}\cdot{x} + 1}{7} < 2^{2023},\] \[\textbf{(4) } S_{2019}=\frac{2^{2019}\cdot{y} + 1}{7} < 2^{2019}.\] From these two equations, we can deduce that both $x$ and $y$ are less than $7$.

Reducing $\textbf{1}$ and $\textbf{2}$ $\pmod{7},$ we see that \[2^{2023}\cdot{x}\equiv 6\pmod{7},\] and \[2^{2019}\cdot{y}\equiv 6\pmod{7}.\]

The powers of $2$ repeat every $3, \pmod{7}.$

Therefore, $2^{2023}\equiv 2 \pmod 7$ and $2^{2019} \equiv 1 \pmod {7}.$ Substituing this back into the above equations, \[2x\equiv{6}\pmod{7}\] and \[y\equiv{6}\pmod{7}.\]

Since $x$ and $y$ are integers less than $7$, the only values of $x$ and $y$ are $3$ and $6$ respectively.

The requested sum is \begin{align*} \frac{S_{2023}-S_{2019}}{2^{2019}} &= \frac{\frac{2^{2023}\cdot{x} + 1}{7} - \frac{2^{2019}\cdot{y} + 1}{7}}{2^{2019}} \\ &= \frac{1}{2^{2019}}\left(\frac{2^{2023}\cdot{3} + 1}{7} -\left(\frac{2^{2019}\cdot{6} + 1}{7} \right)\right) \\ &= \frac{3\cdot{2^4}-6}{7} \\ &= \boxed{\textbf{(A) } 6}. \end{align*} -Benedict T (countmath1)

Video Solutions

https://youtu.be/sBmk7tNSQBA

~ ThePuzzlr

https://youtu.be/2Dw75Zy6yAQ

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution by OmegaLearn Using Binary and Modular Arithmetic

https://youtu.be/s_Bgj9srrXI

~ pi_is_3.14

See Also

2022 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 24 		Followed by
Last problem
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions
2022 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 22 		Followed by
Problem 24
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_10B_Problems/Problem_25&oldid=183591"