|
|
| (22 intermediate revisions by 9 users not shown) |
| Line 1: |
Line 1: |
| − | ==Problem==
| + | #REDIRECT [[2022_AMC_10B_Problems/Problem_25]] |
| − | Let <math>x_0,x_1,x_2,\dotsc</math> be a sequence of numbers, where each <math>x_k</math> is either <math>0</math> or <math>1</math>. For each positive integer <math>n</math>, define
| |
| − | <cmath>S_n = \sum_{k=0}^{n-1} x_k 2^k</cmath>
| |
| − | | |
| − | Suppose <math>7S_n \equiv 1 \pmod{2^n}</math> for all <math>n \geqslant 1</math>. What is the value of the sum
| |
| − | <cmath>x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}</cmath>
| |
| − | | |
| − | | |
| − | <math>\textbf{(A)}~6\qquad\textbf{(B)}~7\qquad\textbf{(C)}~12\qquad\textbf{(D)}~14\qquad\textbf{(E)}~15\qquad</math>
| |
| − | | |
| − | ==Solution==
| |
| − | 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>.
| |
| − | | |
| − | Starting with <math>2019</math>, <cmath>7S_{2019} \equiv 1 \pmod{2^{2019}}</cmath>
| |
| − | <cmath>7S_{2019} = 2^{2019}k + 1</cmath>
| |
| − | Now, take both sides <math>\mod{7}</math>
| |
| − | <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>
| |
| − | Thus, <cmath>0 \equiv k + 1 \pmod{7} \implies k \equiv 6 \pmod{7} \implies k = 7j + 6</cmath>
| |
| − | Therefore, <cmath>7S_{2019} = 2^{2019} (7j + 6) \implies S_{2019} = \frac{2^{2019} (7j + 6) + 1}{7}</cmath>
| |
| − | | |
| − | We may repeat this same calculation with <math>S_{2023}</math> to yield <cmath>S_{2023} = \frac{2^{2023} (7h + 3) + 1}{7}</cmath>
| |
| − | Now, we notice that <math>S_n</math> is basically an integer expressed in binary form with <math>n</math> bits.
| |
| − | This gives rise to a simple inequality, <cmath>0 \leqslant S_n \leqslant 2^n</cmath>
| |
| − | Since the maximum possible number that can be generated with <math>n</math> bits is <cmath>\underbrace{{11111\dotsc1}_2}_{n} = \sum_{k=0}^{n-1} 2^k = 2^n - 1 \leqslant 2^n</cmath>
| |
| − | Looking at our calculations for <math>S_{2019}</math> and <math>S_{2023}</math>, we see that the only valid integers that satisfy that constraint are <math>j = h = 0</math>
| |
| − | <cmath>\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}}</cmath>
| |
