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

AMC 10 · 2020A · #21

학년 8 arithmetic

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

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

📏 긴 풀이 💡 3 개 인사이트

문제

정수

\frac{2²⁸⁹+1}{2¹⁷+1}

을 지수가 엄격히 증가하는 서로 다른 2의 거듭제곱의 합 2^a₁ + 2^a₂ + … + 2^a_k 로 나타낼 때, 항의 개수 k 를 구하세요. 이는 이 정수를 이진법으로 적었을 때 나타나는 1의 개수입니다.

답을 골라 클릭하세요.

(A)

117

(B)

136

(C)

137

(D)

273

(E)

306

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

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #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

289를 거듭제곱으로 바꾸기

289 = 17 × 17 이니 x = 2¹⁷ 로 두면 분수가 깔끔한 $\frac{x¹⁷+1}{x+1}$ 이 된다.

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

2STEP 2

홀수 거듭제곱 인수분해 쓰기

홀수 n 에서 xⁿ+1 = (x+1)(xⁿ⁻¹−…+1) 이므로 몫은 x¹⁶ − x¹⁵ + … − x + 1 — 교대 17 항.

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

3STEP 3

x를 다시 대입하기

x = 2¹⁷을 다시 대입하면 xʲ = 2¹⁷ʲ 이라 몫은 2²⁷² − 2²⁵⁵ + 2²³⁸ − … + 2³⁴ − 2¹⁷ + 1.

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

4STEP 4

부호 붙은 항 짝짓기

부호 붙은 17 항을 8 쌍 (2^A − 2^B)과 외톨이 +1로 묶는다: (2²⁷²−2²⁵⁵) + … + (2³⁴−2¹⁷) + 1.

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

5STEP 5

각 짝을 이진수로 펼치기

각 쌍 2^A − 2^B = 2^B(2¹⁷−1)이고 2¹⁷−1은 17 개 연속 1 비트라 한 쌍이 17 개 거듭제곱으로 펼쳐진다.

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

6STEP 6

지수 구간 나열하기

각 쌍이 너비 17 지수 블록을 채운다 — [17,33], [51,67], …, [255,271] — 서로 겹치지 않는 8 블록.

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

7STEP 7

1의 개수 세기

8 블록이 8 × 17 = 136 비트, 외톨이 2⁰이 하나 더해져 k = 137 → (C).

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

정답

137

크기 확인: 몫은 약

\frac{2²⁸⁹}{2¹⁷}

= 2²⁷²이라 비트 길이가 ≤ 273. 그중 k = 137이 1 비트 — 절반 정도라 교대-후-채움 패턴과 부합. 선택지 (D) 273은 비트 길이 함정, (B) 136은 2⁰을 빠뜨림, (C) 137이 정답. 작은 예 확인:

\frac{2⁹+1}{2³+1}

\frac{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 10 문제는 이미 배운 8학년 지수 법칙만 있으면 풀려요 — x = 2¹⁷이라 이름 붙여 $\frac{x¹⁷+1}{x+1}$ 로 줄이고, 17 개 교대 거듭제곱으로 펼쳐서 쌍으로 묶으면 각 쌍이 17 개 연속 1 비트가 되니 8 × 17 + 1 = 137.

289를 거듭제곱으로 바꾸기
홀수 거듭제곱 인수분해 쓰기
x를 다시 대입하기
부호 붙은 항 짝짓기
각 짝을 이진수로 펼치기
지수 구간 나열하기
1의 개수 세기

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