AMC 10 · 2022 · #25

학년 6 arithmetic

modular-arithmeticp-adic-inversepattern-recognitionrecursive-sequenceexponents easier-related-problempattern-recognitionsystematic-enumeration ↑ 선수 지식: modular-arithmeticrecursive-sequence

📏 긴 풀이 💡 4 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 비트 수열 $x_0, x_1, x_2, \dots \in \{0, 1\}$ 가 모든 $n \ge 1$ 에 대해 $S_n := \sum_{k=0}^{n-1} x_k 2^k$ 가 $7 S_n \equiv 1 \pmod{2^n}$ 을 만족하도록 (각 $x_k$ 가 유일하게) 정해집니다. $x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022}$ 의 값을 구하세요.

주어진 것: $x_k \in \{0, 1\}$ (모든 $k \ge 0$); $S_n = x_0 + 2 x_1 + 4 x_2 + \dots + 2^{n-1} x_{n-1}$; $7 S_n \equiv 1 \pmod{2^n}$ (모든 $n \ge 1$), 이 조건이 각 $x_k$ 를 유일하게 결정; 선택지: (A) $6$, (B) $7$, (C) $12$, (D) $14$, (E) $15$

구하는 것: $x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022}$

이해

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #5 패턴 찾기, #2 빠짐없이 나열하기, #13 대수로 바꾸기, #3 가능성 지우기

도구 #9(더 쉬운 문제) — 인덱스 $2019$ 를 직접 공략 대신 $S_3, S_6, S_9$ 을 손으로 계산해 비트 $x_0, x_1, \dots, x_8$ 을 읽기. 도구 #5(패턴) — 작은 데이터에서 주기 $3$ 패턴이 보일 것. 도구 #2(나열) — 처음 9 비트를 세 개씩 묶어 주기 확인. 도구 #13(대수) — 패턴 확정 후 $k = 2019, 2020, 2021, 2022$ 대입. 도구 #3(가능성 지우기) — 결과를 선택지 $\{6, 7, 12, 14, 15\}$ 와 비교.

실행 — 정답: A

#9 더 쉬운 문제로 줄이기 6.NS.B.4 단계 1

쉬운 사례부터: 작은 $n$ 에서 $7$ 의 $2^n$ 에 대한 곱셈 역원으로 $S_n$ 계산.
$n = 3$: $7 S_3 \equiv 1 \pmod{8}$.
$7 \equiv -1 \pmod 8$ 이라 $S_3 \equiv -1 \equiv 7 \pmod 8$.
$0 \le S_3 < 8$ 에서 $S_3 = 7 = 111_2$, 즉 $x_0, x_1, x_2 = 1, 1, 1$.

$$S_3 = 7 = 111_2 \;\Rightarrow\; x_0, x_1, x_2 = 1, 1, 1$$

💡 6학년 — 작은 $2$ 의 거듭제곱에 대한 $7$ 의 역원을 직접 찾기.

#9 더 쉬운 문제로 줄이기 5.NBT.A.2 단계 2

$n = 6$: $7 S_6 \equiv 1 \pmod{64}$.
$S_6 = 55$ 시도: $7 \cdot 55 = 385 = 6 \cdot 64 + 1$ ✓.
$S_6 = 55 = 32 + 16 + 4 + 2 + 1 = 110111_2$ (낮은 자리부터 $1, 1, 1, 0, 1, 1$).
$x_3, x_4, x_5 = 0, 1, 1$.

$$S_6 = 55 = 110111_2 \;\Rightarrow\; x_3, x_4, x_5 = 0, 1, 1$$

💡 5학년 — 한 비트씩 읽어내기.

#9 더 쉬운 문제로 줄이기 5.NBT.A.2 단계 3

$n = 9$: $7 S_9 \equiv 1 \pmod{512}$.
$S_9 = 439$ 시도: $7 \cdot 439 = 3073 = 6 \cdot 512 + 1$ ✓.
$S_9 = 439 = 256 + 128 + 32 + 16 + 4 + 2 + 1 = 110110111_2$ (비트 $1,1,1,0,1,1,0,1,1$).
$x_6, x_7, x_8 = 0, 1, 1$.

$$S_9 = 439 = 110110111_2 \;\Rightarrow\; x_6, x_7, x_8 = 0, 1, 1$$

💡 5학년 — 더 긴 수에 같은 비트 읽기.

#5 패턴 찾기 4.OA.C.5 단계 4

패턴.
처음 아홉 비트 $(x_0,\dots,x_8) = (1,1,1,\,0,1,1,\,0,1,1)$.
세 개씩 묶으면 인덱스 $3$ 부터 주기 $3$ 의 $(0,1,1)$ 이 반복.
따라서 $k \ge 3$ 일 때: $x_k = 0$ ($k \equiv 0 \pmod 3$), $x_k = 1$ ($k \equiv 1, 2 \pmod 3$).

$$x_k = \begin{cases} 0 & k \equiv 0 \pmod 3 \\ 1 & k \equiv 1, 2 \pmod 3 \end{cases} \quad (k \ge 3)$$

💡 4학년 — 세 묶음 데이터로 주기 $3$ 규칙이 또렷이 드러남.

#2 빠짐없이 나열하기 4.OA.C.5 단계 5

$k = 2019, 2020, 2021, 2022$ 대입.
$2019 = 3 \cdot 673$, $2019 \equiv 0 \pmod 3 \Rightarrow x_{2019} = 0$.
$2020 \equiv 1 \Rightarrow x_{2020} = 1$.
$2021 \equiv 2 \Rightarrow x_{2021} = 1$.
$2022 \equiv 0 \Rightarrow x_{2022} = 0$.

$$x_{2019} = 0, \; x_{2020} = 1, \; x_{2021} = 1, \; x_{2022} = 0$$

💡 4학년 — 규칙으로 각 인덱스 비트 조회.

#3 가능성 지우기 4.OA.A.3 단계 6

목표 계산: $x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022} = 0 + 2 \cdot 1 + 4 \cdot 1 + 8 \cdot 0 = 2 + 4 = 6$.
정답 (A).

$$0 + 2 + 4 + 0 = 6 \;\Rightarrow\; \textbf{(A)}$$

💡 4학년 — 자연수 다단계 연산으로 마무리.

[1] #9 6.NS.B.4 쉬운 사례부터: 작은 $n$ 에서 $7$ 의 $2^n$ 에 대한 곱셈 역원으로 $S_n$ 계산. $n = 3$: $7 S_3 \equiv 1 \

[2] #9 5.NBT.A.2 $n = 6$: $7 S_6 \equiv 1 \pmod{64}$. $S_6 = 55$ 시도: $7 \cdot 55 = 385 = 6 \cdot

[3] #9 5.NBT.A.2 $n = 9$: $7 S_9 \equiv 1 \pmod{512}$. $S_9 = 439$ 시도: $7 \cdot 439 = 3073 = 6 \c

[4] #5 4.OA.C.5 패턴. 처음 아홉 비트 $(x_0,\dots,x_8) = (1,1,1,\,0,1,1,\,0,1,1)$. 세 개씩 묶으면 인덱스 $3$ 부터 주기

[5] #2 4.OA.C.5 $k = 2019, 2020, 2021, 2022$ 대입. $2019 = 3 \cdot 673$, $2019 \equiv 0 \pmod 3 \R

[6] #3 4.OA.A.3 목표 계산: $x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022} = 0 + 2 \cdot 1 + 4 \cdo

검토

합리성 확인: 수치 점검. 패턴 확인은 구체적: 서로 다른 세 $n$ 에서 세 묶음의 비트가 모두 $k \ge 3$ 에서 $(0, 1, 1)$ 로 일치. 처음 묶음 $(1,1,1)$ 은 시작 부분의 특수 케이스. 주기성 이중 확인: $7 S_n \equiv 1 \pmod{2^n}$ 은 $7$ 의 $2$-adic 역원의 부호 부호화, 그리고 $7 = 2^3 - 1$ 이라 $\tfrac{1}{7} = -\tfrac{1}{1 - 2^3}$ 은 $2^3$ 에 대한 기하급수 — 이것이 바로 비트 패턴 주기 $3$ 의 이유. 정답 $6$ 이 (A) 와 일치. 다른 선택지 $7, 12, 14, 15$ 는 비트 하나 오독이나 주기 한 칸 어긋남.

대안 접근: 도구 #13(대수). $7 S_n = k_n \cdot 2^n + 1$, $0 \le S_n < 2^n$ 에서 $k_n \in \{0, \dots, 6\}$ 이 $k_n \cdot 2^n \equiv -1 \equiv 6 \pmod 7$ 로 유일. $2^k \pmod 7$ 은 주기 $3$ 의 $1, 2, 4, 1, 2, 4, \dots$. $2019 \equiv 0 \pmod 3$ 에서 $2^{2019} \equiv 1$, $k_{2019} = 6$. $2023 \equiv 1 \pmod 3$ 에서 $2^{2023} \equiv 2$, $k_{2023} \cdot 2 \equiv 6$, $k_{2023} = 3$. 그러면 $S_{2023} - S_{2019} = \tfrac{3 \cdot 2^{2023} - 6 \cdot 2^{2019}}{7} = \tfrac{(48-6) \cdot 2^{2019}}{7} = 6 \cdot 2^{2019}$, 따라서 목표 $= \tfrac{S_{2023} - S_{2019}}{2^{2019}} = 6$.

사용된 CCSS 표준 (최저 학년 6)

4.OA.A.3 사칙연산을 이용한 다단계 자연수 문제 해결 (마지막 산술 $0 + 2 \cdot 1 + 4 \cdot 1 + 8 \cdot 0 = 6$.)
4.OA.C.5 주어진 규칙으로 수·도형 패턴 만들기 (주기 $3$ 패턴 $x_k = 0, 1, 1$ ($k \bmod 3 = 0, 1, 2$) 을 인덱스 $2019, 2020, 2021, 2022$ 에 적용.)
5.NBT.A.2 10 의 거듭제곱으로 곱할 때 0 의 개수와 소수점 위치 패턴 설명 (이진 전개 $7 = 111_2, 55 = 110111_2, 439 = 110110111_2$ 를 비트별로 읽기.)
6.NS.B.4 두 자연수의 최대공약수·최소공배수 구하기 ($8, 64, 512$ 에 대한 $7$ 의 곱셈 역원 찾기 ("$7$ 에 무엇을 곱해야 나머지 $1$?").)

⭐ 이 AMC 10 문제는 이미 배운 6학년 정수 추론만 있으면 풀려요 — $n = 3, 6, 9$ 의 세 작은 경우로 비트 $x_0, x_1, \dots, x_8$ 을 손으로 계산하면 $k \ge 3$ 에서 주기 $3$ 패턴 $(0,1,1)$ 이 또렷이 보입니다. $2019, 2020, 2021, 2022 \pmod 3$ 조회로 비트 $0, 1, 1, 0$, 목표 $0 + 2 + 4 + 0 = 6$.