|
|
| Line 1: |
Line 1: |
| − | {{duplicate|[[2022 AMC 12B Problems#Problem 23|2022 AMC 12B #23]] and [[2022 AMC 10B Problems#Problem 25|2022 AMC 10B #25]]}}
| + | #REDIRECT [[2022_AMC_10B_Problems/Problem_25]] |
| − | | |
| − | ==Problem==
| |
| − | 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 \geq 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>\mathbb{Z}_{2^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>\text{mod } 7</math>
| |
| − | <cmath>0 \equiv 2^{2019}k + 1 \pmod{7}</cmath>
| |
| − | Using Fermat's Little Theorem, <cmath>2^{2019} = (2^{336})^6 \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) + 1 \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>
| |
| − | ~ <math>\color{magenta} zoomanTV</math>
| |
| − | | |
| − | ==Solution 2 (Base-2 Analysis)==
| |
| − | | |
| − | We solve this problem with base 2.
| |
| − | To avoid any confusion, for a base-2 number, we index the <math>k</math>th rightmost digit as digit <math>k-1</math>.
| |
| − | | |
| − | We have <math>S_n = \left( x_{n-1} x_{n-2} \cdots x_1 x_0 \right)_2</math>.
| |
| − | | |
| − | In the base-2 representation, <math>7 S_n \equiv 1 \pmod{2^n}</math> is equivalent to
| |
| − | <cmath>
| |
| − | \[
| |
| − | \left( x_{n-1} x_{n-2} \cdots x_1 x_0 000 \right)_2
| |
| − | - \left( x_{n-1} x_{n-2} \cdots x_1 x_0 \right)_2
| |
| − | - (1)_2
| |
| − | = \left( \cdots \underbrace{00\cdots 0}_{n \mbox{ digits} } \right)_2 .
| |
| − | \]
| |
| − | </cmath>
| |
| − | | |
| − | In the rest of the analysis, to lighten notation, we ease the base-2 subscription from all numbers.
| |
| − | The equation above can be reformulated as:
| |
| − | | |
| − | \begin{table}
| |
| − | \begin{tabular}{ccccccccc}
| |
| − | & <math>\cdots</math> & 0 & <math>\cdots</math> & 0 & 0 & 0 & 0 & 0 \\
| |
| − | & & & & & & & & 1 \\
| |
| − | <math>+</math>& & <math>x_{n-1}</math> & <math>\cdots</math> & <math>x_4</math> & <math>x_3</math> & <math>x_2</math> & <math>x_1</math> & <math>x_0</math> \\
| |
| − | \hline
| |
| − | & <math>x_{n-1}</math> <math>x_{n-2}</math> <math>x_{n-3}</math> & <math>x_{n-4}</math> & <math>\cdots</math> & <math>x_1</math> & <math>x_0</math> & 0 & 0 & 0\\
| |
| − | \end{tabular}
| |
| − | \end{table}
| |
| − | | |
| − | Therefore, <math>x_0 = x_1 = x_2 = 1</math>, <math>x_3 = 0</math>, and for <math>k \geq 4</math>, <math>x_k = x_{k-3}</math>.
| |
| − | | |
| − | Therefore,
| |
| − | <cmath>
| |
| − | \begin{align*}
| |
| − | x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022}
| |
| − | & = x_3 + 2 x_1 + 4 x_2 + 8 x_3 \\
| |
| − | & = \boxed{\textbf{(A) 6}} .
| |
| − | \end{align*}
| |
| − | </cmath>
| |
| − | | |
| − | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
| |
| − | | |
| − | ==Solution 3 ==
| |
| − | | |
| − | As in Solution <math>1</math>, we note that
| |
| − | | |
| − | <cmath>x_{2019}+2x_{2020}+4x_{2021}+8x_{2022}=\frac{S_{2023}-S_{2019}}{2^{2019}}.</cmath>
| |
| − | | |
| − | We also know that <math>7S_{2023} \equiv 1 \pmod{2^{2023}}</math> and <math>7S_{2019} \equiv 1 \pmod{2^{2019}}</math>, this implies:
| |
| − | | |
| − | <cmath> \textbf{(1) } 7S_{2023}=2^{2023}\cdot{x} + 1 </cmath>
| |
| − | <cmath> \textbf{(2) } 7S_{2019}=2^{2019}\cdot{y} + 1. </cmath>
| |
| − | | |
| − | Dividing by <math>7</math>, we can isolate the previous sums:
| |
| − | | |
| − | <cmath> \textbf{(3) } S_{2023}=\frac{2^{2023}\cdot{x} + 1}{7} </cmath>
| |
| − | <cmath> \textbf{(4) } S_{2019}=\frac{2^{2019}\cdot{y} + 1}{7}. </cmath>
| |
| − | | |
| − | The maximum value of <math>S_n</math> occurs when every <math>x_i</math> is equal to <math>1</math>. Even when this happens, the value of <math>S_n</math> is less than <math>2^n</math>. Therefore, we can construct the following inequalities:
| |
| − | | |
| − | <cmath> \textbf{(3) } S_{2023}=\frac{2^{2023}\cdot{x} + 1}{7} < 2^{2023} </cmath>
| |
| − | <cmath> \textbf{(4) } S_{2019}=\frac{2^{2019}\cdot{y} + 1}{7} < 2^{2019}. </cmath>
| |
| − | | |
| − | From these two equations, we can deduce that both <math>x</math> and <math>y</math> are less than <math>7</math>.
| |
| − | | |
| − | Reducing <math>\textbf{1}</math> and <math>\textbf{2}</math> <math>\pmod{7},</math> we see that
| |
| − | | |
| − | <cmath>2^{2023}\cdot{x}\equiv 6\pmod{7}</cmath>
| |
| − | and
| |
| − | <cmath>2^{2019}\cdot{y}\equiv 6\pmod{7}.</cmath>
| |
| − | | |
| − | The powers of <math>2</math> repeat every <math>3, \pmod{7}.</math>
| |
| − | | |
| − | Therefore, <math>2^{2023}\equiv 2 \pmod 7</math> and <math>2^{2019} \equiv 1 \pmod {7}.</math> Substituing this back into the above equations,
| |
| − | | |
| − | <cmath>2x\equiv{6}\pmod{7}</cmath>
| |
| − | and
| |
| − | <cmath>y\equiv{6}\pmod{7}.</cmath>
| |
| − | | |
| − | Since <math>x</math> and <math>y</math> are integers less than <math>7</math>, the only values of <math>x</math> and <math>y</math> are <math>3</math> and <math>6</math> respectively.
| |
| − | | |
| − | The requested sum is
| |
| − | | |
| − | <cmath>\frac{S_{2023}-S_{2019}}{2^{2019}} = \frac{\frac{2^{2023}\cdot{x} + 1}{7} - \frac{2^{2019}\cdot{y} + 1}{7}}{2^{2019}}</cmath>
| |
| − | | |
| − | <cmath> = \frac{1}{2^{2019}}\left(\frac{2^{2023}\cdot{3} + 1}{7} -\left(\frac{2^{2019}\cdot{6} + 1}{7} \right)\right) </cmath>
| |
| − | | |
| − | <cmath> = \frac{3\cdot{2^4}-6}{7}</cmath>
| |
| − | <cmath> = \boxed{\textbf{(A) 6}}.</cmath>
| |
| − | | |
| − | -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==
| |
| − | {{AMC10 box|year=2022|ab=B|num-b=24|after=Last problem}}
| |
| − | {{AMC12 box|year=2022|ab=B|num-b=22|num-a=24}}
| |
| − | | |
| − | [[Category:Intermediate Number Theory Problems]]
| |
| − | {{MAA Notice}}
| |
