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 "2022 AMC 12B Problems/Problem 23"

(→‎Solution)
m (→‎Solution)
Line 12: Line 12:
 
First, notice that <cmath>x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022} = \frac{S_{2023} - S_{2019}}{2^{2019}}</cmath>
 
First, notice that <cmath>x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022} = \frac{S_{2023} - S_{2019}}{2^{2019}}</cmath>
  
−
Then since <math>S_n</math> is the modular inverse of 7 in <math>Z_{n}</math>, we can perform the Euclidean algorithm to find it for <math>n = 2019,2023</math>.
+
Then since <math>S_n</math> is the modular inverse of 7 in <math>\mathbb{Z}_{n}</math>, we can perform the Euclidean algorithm to find it for <math>n = 2019,2023</math>.
  
 
Starting with <math>2019</math>, <cmath>7S_{2019} \equiv 1 \pmod{2^{2019}}</cmath>
 
Starting with <math>2019</math>, <cmath>7S_{2019} \equiv 1 \pmod{2^{2019}}</cmath>
 
<cmath>7S_{2019} = 2^{2019}k + 1</cmath>
 
<cmath>7S_{2019} = 2^{2019}k + 1</cmath>
−
Now, take both sides <math>\mod{7}</math>
+
Now, take both sides <math>\text{mod } 7</math>
 
<cmath>0 \equiv 2^{2019}k + 1 \pmod{7}</cmath>
 
<cmath>0 \equiv 2^{2019}k + 1 \pmod{7}</cmath>
 
Using Fermat's Little Theorem, <cmath>2^{2019} = (2^{288})^7 \cdot 2^3 \equiv 2^3 \equiv 1 \pmod{7}</cmath>
 
Using Fermat's Little Theorem, <cmath>2^{2019} = (2^{288})^7 \cdot 2^3 \equiv 2^3 \equiv 1 \pmod{7}</cmath>

Revision as of 16:00, 17 November 2022

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\qquad$

Solution

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}_{n}$, we can perform the Euclidean algorithm to find it for $n = 2019,2023$.

Starting with $2019$, \[7S_{2019} \equiv 1 \pmod{2^{2019}}\] \[7S_{2019} = 2^{2019}k + 1\] Now, take both sides $\text{mod } 7$ \[0 \equiv 2^{2019}k + 1 \pmod{7}\] Using Fermat's Little Theorem, \[2^{2019} = (2^{288})^7 \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$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_AMC_12B_Problems/Problem_23&oldid=181945"