AMC 10 · 2009 · #18

학년 8 number-theory

유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint

prime-factorizationexponentsoptimization caseworkbound-inequality-then-enumerate ↑ 선수 지식: prime-factorization

📏 긴 풀이 💡 3 개 인사이트

문제

어떤 수들이 1, 이어지는 0들, 그리고 고정된 두 자릿수로 이루어진다. 그중 하나를 나누는 2의 가장 큰 거듭제곱의 지수를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 극단의 원리

문제가 최댓값을 묻고 있으므로 도구 #14(극단의 원리)가 목표를 정한다: 2의 개수가 가장 커지는 지점을 찾는데, 그곳은 하나의 경계 경우로 드러난다. 그러기 위해 도구 #4(변수 도입하기)로 자릿수 그림 I_k를 깔끔한 식 10^k+2+64, 나아가 2^k+25^k+2+2⁶으로 바꿔 2가 나오는 두 근원을 드러낸다. 도구 #7(작은 문제로 쪼개기)은 두 지수 k+2와 6을 비교해 작업을 나눈다: 둘이 다르면 작은 쪽이 개수를 지배해 여분의 2가 생기지 않고, 둘이 같을 때만 두 조각이 합쳐져 2를 더 내놓을 수 있다. 마지막으로 도구 #6(추측하고 확인하기)으로 그 균형점(k=4)을 직접 확인해 정확한 개수를 읽어낸다.

1STEP 1

수를 식으로 나타내기

식이 자릿수 설명을 대신한다.

I_k = 10^k+2 + 64

2STEP 2

각 조각을 2와 5로 분해하기

각 조각이 2와 5의 거듭제곱으로 쪼개진다.

I_k = 2^k+25^k+2 + 2⁶

3STEP 3

더 작은 2의 거듭제곱을 밖으로 빼기

더 작은 거듭제곱을 빼내면 경우가 나뉜다.

먼저 2^min(k+2, 6)개의 2가 빠진다

4STEP 4

경우 k ＜ 4: 작은 쪽이 지배

경계 아래에서는 한쪽이 지배해 개수가 5로 제한된다.

I_k=2^k+2(5^k+2+2⁴-k), N(k)=k+2 ≤ 5

5STEP 5

경우 k ＞ 4: 64의 여섯 개 2에 묶임

그 위에서는 다른 쪽이 개수를 6으로 제한한다.

I_k=2⁶(2^k-45^k+2+1), N(k)=6

6STEP 6

경계 경우 k = 4: 양쪽이 균형

경계에서는 둘이 균형을 이뤄 여분의 인수가 생긴다.

I₄=2⁶(5⁶+1)=2⁶·15626=2⁷·7813, N(4)=7

7STEP 7

최댓값 고르기

그래서 최댓값은 7이다, 보기 (B).

max N(k)=max{5,6,7}=7=(B)

정답

답은 적어도 6이어야 한다. 64=2⁶이 상쇄가 일어나기 전 여섯 개의 2를 보장하고 선택지도 6부터 시작하기 때문이다. k=4에서의 여분의 2는 실제로 존재한다: 1000064=2⁷·7813이고 7813은 홀수라 정확히 일곱 개의 2이며 그 이상은 없다. 다른 모든 k에서는 괄호가 홀수로 나와 개수가 6 이하로 묶였으므로 7은 정말로 넘어설 수 없다. 이는 선택지 (B)와 맞고 8,9,10을 배제한다. 그 값들은 괄호가 여분의 2를 둘 이상 지녀야 하는데 5⁶+1은 오직 하나만 가지므로 불가능하다.

💡핵심 정리

수를 10^k+2에서 나온 2들과 64에서 나온 2들로 나누어 보라. 두 더미가 정확히 같아질 때에만 여분의 2가 하나 더 생기는데, 그것이 k=4에서 일어나 최댓값 N=7, 곧 선택지 (B)를 준다.

수를 식으로 나타내기
각 조각을 2와 5로 분해하기
더 작은 2의 거듭제곱을 밖으로 빼기
경우 k ＜ 4: 작은 쪽이 지배
경우 k ＞ 4: 64의 여섯 개 2에 묶임
경계 경우 k = 4: 양쪽이 균형
최댓값 고르기