AMC 10 · 2020 · #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¹⁷ 로 치환해 $\frac{x¹⁷+1}{x+1}$ 로 줄이고, 더 작은 $\frac{x³+1}{x+1}$ 을 먼저 확인해 구조를 본다. 도구 #5(패턴): 교대 다항식 몫 x¹⁶-x¹⁵+…+1 의 깔끔한 규칙. 도구 #7(작은 문제로 쪼개기): 뺄셈 2^A - 2^B 를 1 비트 연속 띠로 분해. 도구 #2(빠짐없이 나열): 각 쌍이 17 개 비트를 만든다는 사실을 알면 블록들을 나열·합산만 하면 됨.

1STEP 1

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

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

\frac{x¹⁷+1}{x+1}

, x = 2¹⁷

2STEP 2

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

\frac{x¹⁷+1}{x+1}

= x¹⁶ - x¹⁵ + x¹⁴ - … + x² - x + 1

3STEP 3

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

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.

비슷한 유형 더 풀어보기