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 10B Problems/Problem 25"

(→‎Solution (Base-2 Analysis))
(→‎Solution (Base-2 Analysis))
Line 37: Line 37:
 
The equation above can be reformulated as:
 
The equation above can be reformulated as:
  
−
<math></math>
+
\begin{table}
 
\begin{tabular}{ccccccccc}
 
\begin{tabular}{ccccccccc}
 
       & <math>\cdots</math> & 0 & <math>\cdots</math> & 0 & 0 & 0 & 0 & 0 \\
 
       & <math>\cdots</math> & 0 & <math>\cdots</math> & 0 & 0 & 0 & 0 & 0 \\
Line 45: Line 45:
 
       & <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\\
 
       & <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{tabular}
−
<math></math>
+
\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, <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>.

Revision as of 14:17, 17 November 2022

Problem

Let $x_0, x_1, x_2, \cdots$ 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 $7 S_n \equiv 1 \pmod{2^n}$ for all $n \geq 1$. What is the value of the sum \[ x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022} ? \]

Solution (Base-2 Analysis)

We solve this problem with base 2. To avoid any confusion, for a base-2 number, we index the $k$th rightmost digit as digit $k-1$.

We have $S_n = \left( x_{n-1} x_{n-2} \cdots x_1 x_0 \right)_2$.

In the base-2 representation, $7 S_n \equiv 1 \pmod{2^n}$ is equivalent to \[ \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 . \]

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} 

     & $\cdots$ & 0 & $\cdots$ & 0 & 0 & 0 & 0 & 0 \\
     &   &   &   &   &   &   &   & 1 \\
     $+$&  & $x_{n-1}$ & $\cdots$ & $x_4$ & $x_3$ & $x_2$ & $x_1$ & $x_0$ \\
   \hline %or \bottomrule if using the `booktabs` package
     & $x_{n-1}$ $x_{n-2}$ $x_{n-3}$ & $x_{n-4}$ & $\cdots$ & $x_1$ & $x_0$ & 0 & 0 & 0\\
   \end{tabular}

\end{table}

Therefore, $x_0 = x_1 = x_2 = 1$, $x_3 = 0$, and for $k \geq 4$, $x_k = x_{k-3}$.

Therefore, \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*}

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

Video Solution

https://youtu.be/2Dw75Zy6yAQ

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

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