AMC 10 · 2020 · #19

학년 8 number-theory

유형 Arithmetic Expression Decomposition └ 세부 유형 Multi-Segment Path or Count Sum

polynomial-factoringbase-conversionexponentssequences-geometricpattern-recognition identify-subproblemspattern-recognitioneasier-related-problem ↑ 선수 지식: polynomial-factoringbase-conversion

📏 긴 풀이 💡 3 개 인사이트

문제

어떤 큰 정수를 서로 다른 2의 거듭제곱의 합으로 씁니다. 지수는 엄격히 커지는 순서입니다. 이때 항이 몇 개인지, 즉 이 수를 2진법으로 썼을 때 1이 몇 개인지 구하세요.

답을 골라 클릭하세요.

(A)

117

(B)

136

(C)

137

(D)

273

(E)

306

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #9(더 쉬운 문제): 지수 289, 17이 너무 크니 x = 2¹⁷로 치환해 (x¹⁷+1)/(x+1)로 줄이고, 더 작은 (x³+1)/(x+1)을 먼저 확인해 구조를 본다. 도구 #5(패턴): 교대 다항식 몫 x¹⁶-x¹⁵+…+1의 깔끔한 규칙. 도구 #7(작은 문제로 쪼개기): 뺄셈 2^A - 2^B 를 1 비트 연속 띠로 분해. 도구 #2(빠짐없이 나열): 각 쌍이 17 개 비트를 만든다는 사실을 알면 블록들을 나열·합산만 하면 됨.

1STEP 1

치환해서 단순화하기

치환하면 익숙한 다항식 나눗셈이 됩니다.

(2²⁸⁹+1)/(2¹⁷+1) = (x¹⁷+1)/(x+1), x = 2¹⁷

2STEP 2

몫 쓰기

몫은 부호가 번갈아 나옵니다.

(x¹⁷+1)/(x+1) = x¹⁶ - x¹⁵ + x¹⁴ - … + x² - x + 1

3STEP 3

거듭제곱으로 되돌리기

치환을 되돌립니다.

2²⁷² - 2²⁵⁵ + 2²³⁸ - 2²²¹ + … + 2³⁴ - 2¹⁷ + 2⁰

4STEP 4

이웃끼리 묶기

이웃끼리 묶어 음수를 없앱니다.

(2²⁷²-2²⁵⁵)_쌍 1 + (2²³⁸-2²²¹)_쌍 2 + … + (2³⁴-2¹⁷)_쌍 8 + 1

5STEP 5

한 묶음 펼치기

한 묶음이 연속된 덩어리가 됩니다.

2^A - 2^B = 2^B(2¹⁷-1) = 2^A-1 + 2^A-2 + … + 2^B+1 + 2^B

6STEP 6

덩어리 세기

덩어리 개수와 폭을 셉니다.

블록들: [17,33], [51,67], [85,101], …, [255,271]; 8 개 블록, 각 너비 17

7STEP 7

모두 더하기

마지막 1까지 더하면 137입니다.

k = 8 × 17 + 1 = 136 + 1 = 137 → (C)

정답

137

크기 확인: 몫은 약 2²⁸⁹/2¹⁷ = 2²⁷²이라 비트 길이가 ≤ 273. 그중 k = 137이 1 비트 — 절반 정도라 교대-후-채움 패턴과 부합. 선택지 (D) 273은 비트 길이 함정, (B) 136은 2⁰을 빠뜨림, (C) 137이 정답. 작은 예 확인: (2⁹+1)/(2³+1) = 513/9 = 57 = 32 + 16 + 8 + 1 = 2⁵ + 2⁴ + 2³ + 2⁰으로 k = 4. 같은 공식: 9 = 3 · 3, 교대 다항식 항 3 개(1 쌍 + 끝의 1), k = 1 · 3 + 1 = 4. 일치.

💡핵심 정리

이 AMC 12 문제는 이미 배운 8학년 지수 법칙만 있으면 풀려요 — x = 2¹⁷이라 이름 붙여 (x¹⁷+1)/(x+1)로 줄이고, 17 개 교대 거듭제곱으로 펼쳐서 쌍으로 묶으면 각 쌍이 17 개 연속 1 비트가 되니 8 × 17 + 1 = 137.