AMC 10 · 2009 · #25

학년 8 number-theory

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

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

📏 긴 풀이 💡 3 개 인사이트

문제

각 양의 정수 k에 대해 I_k는 맨 앞에 1, 그다음 0이 정확히 k개, 마지막에 6과 4가 오는 수이다. 예를 들어 I_1 = 1064이다. N(k)는 I_k가 2로 나누어지는 횟수, 즉 I_k의 소인수분해에서 2의 지수라고 하자. k가 양의 정수 전체를 움직일 때 N(k)가 가질 수 있는 최댓값을 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 극단의 원리

문제가 최댓값을 묻고 있으므로 도구 #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

수를 식으로 나타내기

끝 두 자리는 고정된 64이고 맨 앞 1은 $k+2$ 번째 자리이므로 $I_k=10^{k+2}+64$ 이다.

I_k = 10^k+2 + 64

2STEP 2

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

$10=2\cdot5$ 이므로 $I_k=2^{k+2}5^{k+2}+2^6$ 이 되어 2의 더미가 둘로 갈린다.

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

3STEP 3

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

두 항이 함께 가진 2만 밖으로 나오므로 $k+2$ 와 6 중 작은 쪽이 기준이고, 경우가 셋으로 갈린다.

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

4STEP 4

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

$k=1,2,3$ 이면 괄호 $5^{k+2}+2^{4-k}$ 이 홀수+짝수라 홀수이므로 $N(k)=k+2$ 로 많아야 5이다.

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

5STEP 5

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

$k \ge 5$ 이면 꼬리가 약해 $I_k=2^6(2^{k-4}5^{k+2}+1)$ 이고 괄호는 짝수+1로 홀수라 $N(k)$ 는 6에서 멈춘다.

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

6STEP 6

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

$k=4$ 에서는 두 더미가 같아 $I_4=2^6(5^6+1)=2^<span class="hl-ask">7</span>\cdot7813$ 이고 7813은 홀수라 $N(4)$ 는 7이다.

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

7STEP 7

최댓값 고르기

세 경우가 각각 많아야 5, 정확히 6, 그리고 7을 주므로 최댓값은 7이고 k=4에서만 도달한다.

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: 양쪽이 균형
최댓값 고르기