AMC 10 · 2022 · #25

학년 6 arithmetic

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

📏 긴 풀이 💡 4 개 인사이트

문제

비트 수열 x₀, x₁, x₂, … ∈ {0, 1} 가 모든 n ≥ 1 에 대해 S_n := Σ_k=0ⁿ⁻¹ x_k 2^k 가 7 S_n ≡ 1 (mod 2ⁿ) 을 만족하도록 (각 x_k 가 유일하게) 정해집니다. x₂019 + 2 x₂020 + 4 x₂021 + 8 x₂022 의 값을 구하세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 더 쉬운 문제로 줄이기

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

1STEP 1

n = 3: 7 ≡ -1 (mod 8) 이라 S₃ = 7 = 111₂, 즉 x₀, x₁, x₂ = 1, 1, 1.

S₃ = 7 = 111₂ → x₀, x₁, x₂ = 1, 1, 1

2STEP 2

n = 6: S₆ = 55 = 110111₂ 를 낮은 자리부터 읽으면 x₃, x₄, x₅ = 0, 1, 1.

S₆ = 55 = 110111₂ → x₃, x₄, x₅ = 0, 1, 1

3STEP 3

n = 9: S₉ = 439 = 110110111₂, 낮은 비트를 읽으면 x₆, x₇, x₈ = 0, 1, 1.

S₉ = 439 = 110110111₂ → x₆, x₇, x₈ = 0, 1, 1

4STEP 4

처음 아홉 비트를 세 개씩 묶으면 k ≥ 3 에서 주기 3 패턴 (0, 1, 1) 이 드러납니다.

x_k = 0 & k ≡ 0 (mod 3) ; 1 & k ≡ 1, 2 (mod 3) (k ≥ 3)

5STEP 5

3 으로 나눈 나머지로 조회하면 x₂019 = 0, x₂020 = 1, x₂021 = 1, x₂022 = 0.

x₂019 = 0, x₂020 = 1, x₂021 = 1, x₂022 = 0

6STEP 6

가중치 1, 2, 4, 8 로 합치면 0 + 2 + 4 + 0 = 6, 정답 (A).

0 + 2 + 4 + 0 = 6 → (A)

정답

수치 점검. 패턴 확인은 구체적: 서로 다른 세 n 에서 세 묶음의 비트가 모두 k ≥ 3 에서 (0, 1, 1) 로 일치. 처음 묶음 (1,1,1) 은 시작 부분의 특수 케이스. 주기성 이중 확인: 7 S_n ≡ 1 (mod 2ⁿ) 은 7 의 2-adic 역원의 부호 부호화, 그리고 7 = 2³ - 1 이라

\frac{1}{7}

-\frac{1}{1 - 2³}

은 2³ 에 대한 기하급수 — 이것이 바로 비트 패턴 주기 3 의 이유. 정답 6 이 (A) 와 일치. 다른 선택지 7, 12, 14, 15 는 비트 하나 오독이나 주기 한 칸 어긋남.

💡핵심 정리

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