AMC 10 · 2020 · #21

학년 8 arithmetic

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

📏 긴 풀이 💡 3 개 인사이트

문제

There exists a unique strictly increasing sequence of nonnegative integers $a_1 < a_2 < … < a_k$ such that $\frac{2^{289}+1}{2^{17}+1} = 2^{a_1} + 2^{a_2} + … + 2^{a_k}.$ What is $k?$

$\textbf{(A) } 117 \qquad \textbf{(B) } 136 \qquad \textbf{(C) } 137 \qquad \textbf{(D) } 273 \qquad \textbf{(E) } 306$

답을 골라 클릭하세요.

(A)

117

(B)

136

(C)

137

(D)

273

(E)

306

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 정수 $\frac{2^{289}+1}{2^{17}+1}$ 을 지수가 엄격히 증가하는 서로 다른 $2$ 의 거듭제곱의 합 $2^{a_1} + 2^{a_2} + \cdots + 2^{a_k}$ 로 나타낼 때, 항의 개수 $k$ 를 구하세요. 이는 이 정수를 이진법으로 적었을 때 나타나는 $1$ 의 개수입니다.

주어진 것: 분자 $2^{289}+1$, 분모 $2^{17}+1$; $289 = 17 \times 17$ 이므로 $x = 2^{17}$ 로 두면 분자·분모는 $x^{17}+1$ 과 $x+1$ 구조; 결과는 지수가 엄격히 증가하는 서로 다른 $2$ 의 거듭제곱의 합; 선택지: (A) $117$, (B) $136$, (C) $137$, (D) $273$, (E) $306$

구하는 것: $k$ = 항의 개수 = 이진수의 $1$ 비트 개수

이해

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #5 패턴 찾기, #7 작은 문제로 쪼개기, #2 빠짐없이 나열하기

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

실행 — 정답: C

#9 더 쉬운 문제로 줄이기 8.EE.A.1 단계 1

$289 = 17 \times 17$ 임에 주목해 $x = 2^{17}$ 로 두자.
그러면 $2^{289} = (2^{17})^{17} = x^{17}$ 이고, 식은 $\frac{x^{17}+1}{x+1}$ 이 된다.
친숙한 다항식 나눗셈 형태.

$$\dfrac{2^{289}+1}{2^{17}+1} = \dfrac{x^{17}+1}{x+1}, \quad x = 2^{17}$$

💡 $x = 2^{17}$ 이라는 이름표만 붙여도 무서운 식이 친숙한 분수가 된다.

#5 패턴 찾기 8.EE.A.1 단계 2

홀수 $n$ 에 대해 $x^n + 1 = (x+1)(x^{n-1} - x^{n-2} + \cdots - x + 1)$ 이라는 항등식이 성립한다.
$n=3$ 으로 확인: $(x+1)(x^2-x+1) = x^3 + 1$.
같은 꼴이 $n=17$ 에도 적용 — 교대 부호로 $17$ 개 항.

$$\dfrac{x^{17}+1}{x+1} = x^{16} - x^{15} + x^{14} - \cdots + x^2 - x + 1$$

💡 $x^3+1$ 을 인수분해하는 같은 패턴이 $x^{17}+1$ 에도 — 단지 더 길 뿐.

#9 더 쉬운 문제로 줄이기 8.EE.A.1 단계 3

$x = 2^{17}$ 을 다시 대입.
$x^j = 2^{17j}$ 이므로 몫은 $17$ 개의 $2$ 의 거듭제곱이 교대 부호로 합쳐진 식이 된다: 지수 $272, 255, 238, \ldots, 34, 17, 0$, 부호 $+, -, +, -, \ldots, +, -, +$.

$$2^{272} - 2^{255} + 2^{238} - 2^{221} + \cdots + 2^{34} - 2^{17} + 2^0$$

💡 다항식 한 항이 $2$ 의 한 거듭제곱이 되고, 부호는 교대, 마지막은 $+1$.

#7 작은 문제로 쪼개기 8.EE.A.1 단계 4

부호 붙은 항은 총 $17$ 개 — 양수 $9$ 개(지수 $272, 238, 204, \ldots, 34, 0$), 음수 $8$ 개(지수 $255, 221, \ldots, 17$).
양수와 바로 뒤 음수를 한 쌍으로 묶으면 $(2^{272} - 2^{255}) + (2^{238} - 2^{221}) + \cdots + (2^{34} - 2^{17})$ 의 $8$ 쌍, 그리고 마지막 $+1$ 이 혼자 남는다.

$$\underbrace{(2^{272}-2^{255})}_{\text{쌍 1}} + \underbrace{(2^{238}-2^{221})}_{\text{쌍 2}} + \cdots + \underbrace{(2^{34}-2^{17})}_{\text{쌍 8}} + 1$$

💡 $+, -$ 인접 항을 $8$ 쌍으로 묶고, 맨 오른쪽 $+1$ 만 짝이 없다.

#9 더 쉬운 문제로 줄이기 8.EE.A.1 단계 5

각 쌍은 $2^A - 2^B$, $A - B = 17$.
작은 쪽을 묶어내면 $2^A - 2^B = 2^B(2^{17} - 1)$.
핵심 사실: $2^{17} - 1 = 2^{16} + 2^{15} + \cdots + 2^1 + 2^0$ — 이진수로 $1$ 이 $17$ 개 연속(작은 예: $2^3 - 1 = 4 + 2 + 1$).
따라서 한 쌍은 정확히 $17$ 개의 서로 다른 $2$ 의 거듭제곱으로 펼쳐진다.

$$2^A - 2^B = 2^B(2^{17}-1) = 2^{A-1} + 2^{A-2} + \cdots + 2^{B+1} + 2^B$$

💡 $2^{17}-1$ 은 이진수로 $1$ 이 $17$ 개 — 작은 패턴이 $8$ 번 반복.

#2 빠짐없이 나열하기 8.EE.A.1 단계 6

지수 블록 나열.
쌍 $i$ ($i = 1, \ldots, 8$) 는 $[B_i, B_i + 16]$ 을 채우는데 $B_8 = 17, B_7 = 51, \ldots, B_1 = 255$.
구체적으로 쌍 8은 $[17, 33]$, 쌍 7은 $[51, 67]$, 쌍 6은 $[85, 101]$, $\ldots$, 쌍 1은 $[255, 271]$.
각 블록은 너비 $17$ 이고 블록 사이 간격이 $17$ 이라 서로 겹치지 않는다.

$$\text{블록들: } [17,33], [51,67], [85,101], \ldots, [255,271]; \;\; 8 \text{ 개 블록, 각 너비 } 17$$

💡 각 쌍이 지수 $17$ 칸짜리 깔끔한 창문을 채운다 — 겹침 없음.

#2 빠짐없이 나열하기 8.EE.A.1 단계 7

비트 세기.
$8$ 개 블록이 $8 \times 17 = 136$ 개의 서로 다른 지수를 만든다.
남은 $+1 = 2^0$ 의 지수 $0$ 은 가장 작은 블록 시작 $17$ 보다 작으므로 새 비트.
합 $136 + 1 = 137$.

$$k = 8 \times 17 + 1 = 136 + 1 = 137 \Rightarrow \textbf{(C)}$$

💡 $17$ 비트 블록 $8$ 개 더하기 외톨이 $1$ 비트 $=137$.

[1] #9 8.EE.A.1 $289 = 17 \times 17$ 임에 주목해 $x = 2^{17}$ 로 두자. 그러면 $2^{289} = (2^{17})^{17} = x^

[2] #5 8.EE.A.1 홀수 $n$ 에 대해 $x^n + 1 = (x+1)(x^{n-1} - x^{n-2} + \cdots - x + 1)$ 이라는 항등식이 성립한다.

[3] #9 8.EE.A.1 $x = 2^{17}$ 을 다시 대입. $x^j = 2^{17j}$ 이므로 몫은 $17$ 개의 $2$ 의 거듭제곱이 교대 부호로 합쳐진 식이 된

[4] #7 8.EE.A.1 부호 붙은 항은 총 $17$ 개 — 양수 $9$ 개(지수 $272, 238, 204, \ldots, 34, 0$), 음수 $8$ 개(지수 $25

[5] #9 8.EE.A.1 각 쌍은 $2^A - 2^B$, $A - B = 17$. 작은 쪽을 묶어내면 $2^A - 2^B = 2^B(2^{17} - 1)$. 핵심 사실:

[6] #2 8.EE.A.1 지수 블록 나열. 쌍 $i$ ($i = 1, \ldots, 8$) 는 $[B_i, B_i + 16]$ 을 채우는데 $B_8 = 17, B_7 =

[7] #2 8.EE.A.1 비트 세기. $8$ 개 블록이 $8 \times 17 = 136$ 개의 서로 다른 지수를 만든다. 남은 $+1 = 2^0$ 의 지수 $0$ 은

검토

합리성 확인: 크기 확인: 몫은 약 $\frac{2^{289}}{2^{17}} = 2^{272}$ 이라 비트 길이가 $\le 273$. 그중 $k = 137$ 이 $1$ 비트 — 절반 정도라 교대-후-채움 패턴과 부합. 선택지 (D) $273$ 은 비트 길이 함정, (B) $136$ 은 $2^0$ 을 빠뜨림, (C) $137$ 이 정답. 작은 예 확인: $\frac{2^9+1}{2^3+1} = \frac{513}{9} = 57 = 32 + 16 + 8 + 1 = 2^5 + 2^4 + 2^3 + 2^0$ 으로 $k = 4$. 같은 공식: $9 = 3 \cdot 3$, 교대 다항식 항 $3$ 개($1$ 쌍 $+$ 끝의 $1$), $k = 1 \cdot 3 + 1 = 4$. 일치.

대안 접근: 도구 #5(패턴 찾기) 만으로: 더 작은 예 $\frac{2^9+1}{2^3+1}$ ($n=3$, $k=4$), $\frac{2^{25}+1}{2^5+1}$ ($n=5$, $k = 2 \cdot 5 + 1 = 11$) 로 일반 공식을 추측 — 홀수 $n$ 에 대해 $\frac{2^{n^2}+1}{2^n+1}$ 의 $k = \frac{n-1}{2} \cdot n + 1$. $n=17$ 대입: $k = 8 \cdot 17 + 1 = 137$. 패턴 귀납만으로 같은 답.

사용된 CCSS 표준 (최저 학년 8)

8.EE.A.1 정수 지수의 성질을 이해하고 적용하기 ($2^{289} = (2^{17})^{17}$ 으로 다시 쓰기, $2^A - 2^B = 2^B(2^{A-B}-1)$ 인수분해, $2^{17}-1$ 을 서로 다른 $2$ 의 거듭제곱의 합으로 전개.)

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

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: C

검토

사용된 CCSS 표준 (최저 학년 8)

비슷한 유형 더 풀어보기