경시 · AMC 대비 · 4단계 중 4

AMC 10 · 2022B · #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₂₀₁₉ + 2 x₂₀₂₀ + 4 x₂₀₂₁ + 8 x₂₀₂₂ 의 값을 구하세요.

답을 골라 클릭하세요.

(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

8을 법으로 7의 역원 구하기

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

64를 법으로 7의 역원 구하기

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

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

3STEP 3

512를 법으로 7의 역원 구하기

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₂₀₁₉ = 0, x₂₀₂₀ = 1, x₂₀₂₁ = 1, x₂₀₂₂ = 0.

x₂₀₁₉ = 0, x₂₀₂₀ = 1, x₂₀₂₁ = 1, x₂₀₂₂ = 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.

8을 법으로 7의 역원 구하기
64를 법으로 7의 역원 구하기
512를 법으로 7의 역원 구하기
반복되는 자릿수 규칙 찾기
네 자리 값 읽어내기
가중치 붙여 더하기

가족의 부모 대시보드는 sensimlab.com에 있습니다.