|
|
| Line 1: |
Line 1: |
| − | ==Problem==
| + | #REDIRECT [[2022_AMC_12B_Problems/Problem_23]] |
| − | | |
| − | Let <math>x_0, x_1, x_2, \cdots</math> be a sequence of numbers, where each <math>x_k</math> is either 0 or 1. For each positive
| |
| − | integer <math>n</math>, define
| |
| − | <cmath>
| |
| − | \[
| |
| − | S_n = \sum_{k=0}^{n-1} x_k 2^k .
| |
| − | \]
| |
| − | </cmath>
| |
| − | | |
| − | Suppose <math>7 S_n \equiv 1 \pmod{2^n}</math> for all <math>n \geq 1</math>.
| |
| − | What is the value of the sum
| |
| − | <cmath>
| |
| − | \[
| |
| − | x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022} ?
| |
| − | \]
| |
| − | </cmath>
| |
| − | | |
| − | ==Solution (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 %or \bottomrule if using the `booktabs` package
| |
| − | & <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)
| |
| − | | |
| − | ==Video Solution==
| |
| − | | |
| − | https://youtu.be/2Dw75Zy6yAQ
| |
| − | | |
| − | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
| |
