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

2022 AMC 10B Problems/Problem 25

Revision as of 15:16, 17 November 2022 by Stevenyiweichen (talk | contribs) (Created page with "==Problem== 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 <c...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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{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}

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=181857"