AMC 10 · 2009 · #25

학년 8 number-theory

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

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

📏 긴 풀이 💡 3 개 인사이트

문제

$k > 0$ 에 대하여, $I_k = 10\ldots 064$ 라 하자. 여기서 $1$ 과 $6$ 사이에는 $k$ 개의 $0$ 이 있다. $N(k)$ 를 $I_k$ 의 소인수분해에 나타나는 $2$ 의 개수(즉 $2$ 의 지수)라고 하자. $N(k)$ 의 최댓값은 얼마인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 각 $k>0$에 대해 $I_k$는 맨 앞에 $1$, 그다음 $0$이 $k$개, 마지막에 $6$과 $4$가 오는 수이다 (즉 $I_k=1\underbrace{0\cdots0}_{k}64$). $N(k)$를 $I_k$를 $2$로 나눌 수 있는 횟수($I_k$의 소인수분해에서 $2$의 지수)라 하자. $k$가 양의 정수 전체를 움직일 때 $N(k)$가 가질 수 있는 최댓값을 구하여라.

주어진 것: $I_k$는 맨 앞이 $1$, 그다음 $0$이 정확히 $k$개, 마지막이 $64$이다; $N(k)$는 $I_k$에 들어 있는 $2$의 인수 개수($2$진 값매김)이다; $k$는 양의 정수이다; 선택지: $6,\ 7,\ 8,\ 9,\ 10$

구하는 것: 모든 양의 정수 $k$에 대한 $N(k)$의 최댓값

이해

계획

주요 도구: #14 극단의 원리

보조 도구: #4 변수 도입하기, #7 작은 문제로 쪼개기, #6 추측하고 확인하기

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

실행 — 정답: B

#4 변수 도입하기 5.NBT.A.2 단계 1

수를 식으로 나타내기

자릿값을 읽자.
끝 두 자리는 $6$(십의 자리)과 $4$(일의 자리)이므로 고정된 수 $64$를 이룬다.
그 위에 $0$이 $k$개, 다시 그 위에 맨 앞의 $1$이 있다.
자리를 세면 $1$은 일의 자리에서 왼쪽으로 $k+2$칸 떨어져 있으므로 $10^{k+2}$을 뜻한다.
따라서 $I_k=10^{k+2}+64$이다.
확인하면 $k=1$일 때 $10^3+64=1064$로, $1$ 뒤에 $0$ 하나, 그다음 $64$이다.

$$I_k = 10^{k+2} + 64$$

💡 $0$을 하나 더할 때마다 맨 앞 $1$이 한 자리씩 밀려 그 자릿값이 $10$배가 된다.

#4 변수 도입하기 8.EE.A.1 단계 2

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

$2$의 인수는 반드시 두 항 중 하나에서 나오므로 각각 소인수분해하자.
$10=2\cdot5$이므로 $10^{k+2}=2^{k+2}\,5^{k+2}$이고, 꼬리 부분은 $64=2^6$이다.
따라서 $I_k=2^{k+2}5^{k+2}+2^6$이다.
이제 문제는 두 덩어리의 $2$에 붙은 지수 $k+2$와 $6$에 관한 것이 된다.

$$I_k = 2^{k+2}5^{k+2} + 2^{6}$$

💡 $10$의 거듭제곱은 짝지어진 $2$와 $5$일 뿐이므로 이를 갈라놓으면 $2$가 어디 있는지 정확히 보인다.

#7 작은 문제로 쪼개기 6.NS.B.4 단계 3

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

$2^{k+2}5^{k+2}$과 $2^6$을 더할 때 밖으로 뺄 수 있는 $2$는 두 항이 함께 가진 만큼, 즉 두 지수 $k+2$와 $6$ 중 작은 쪽까지의 $2$뿐이다.
그것을 빼내고 나면 괄호 안에 남는 것이 여분의 $2$가 더 있는지를 결정한다.
이는 자연스럽게 세 가지 작은 문제로 갈린다: $k+2$가 $6$보다 작을 때, 클 때, 정확히 같을 때이다.

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

💡 합이 $2^m$으로 나누어지는 정도는 두 부분이 함께 가진 만큼까지뿐이라, 약한 항이 공유되는 $2$를 제한한다.

#7 작은 문제로 쪼개기 4.OA.B.4 단계 4

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

$k+2<6$(즉 $k=1,2,3$)이면 $2^{k+2}$을 빼내어 $I_k=2^{k+2}\big(5^{k+2}+2^{\,4-k}\big)$을 얻는다.
안에서 $5^{k+2}$은 홀수이고 $4-k\ge1$이므로 $2^{\,4-k}$은 짝수라, 홀수 $+$ 짝수 $=$ 홀수이다.
괄호에는 더 이상 $2$가 없으므로 $N(k)=k+2$이다.
이 경우 최선은 $k=3$으로 $N(3)=5$이다.

$$I_k=2^{k+2}\big(5^{k+2}+2^{4-k}\big),\quad N(k)=k+2\le 5$$

💡 홀수 하나 더하기 짝수 하나는 언제나 홀수라, 남은 부분은 여분의 $2$를 전혀 못 준다.

#7 작은 문제로 쪼개기 4.OA.B.4 단계 5

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

$k+2>6$(즉 $k\ge5$)이면 꼬리 $2^6$이 약한 항이므로 $2^6$을 빼낸다: $I_k=2^6\big(2^{\,k-4}5^{k+2}+1\big)$.
$k-4\ge1$이므로 $2^{\,k-4}5^{k+2}$은 짝수이고 짝수 $+1$은 홀수이다.
따라서 괄호는 홀수이고 $k$가 아무리 커져도 $N(k)=6$으로 정확히 고정된다.
$0$을 더 붙여도 결코 도움이 되지 않는다.

$$I_k=2^6\big(2^{k-4}5^{k+2}+1\big),\quad N(k)=6$$

💡 $64$가 더 작은 $2$ 더미가 되면, 거기에 짝수를 더해도 홀수가 남으므로 개수가 $6$에서 멈춘다.

#6 추측하고 확인하기 6.NS.B.3 단계 6

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

남은 유일한 경우는 $k+2=6$, 즉 $k=4$로, 두 항이 모두 정확히 $2^6$을 지닌다: $I_4=2^6\,5^6+2^6=2^6\big(5^6+1\big)$.
이제 괄호가 짝수가 될 수 있다.
$5^6=15625$이므로 $5^6+1=15626=2\cdot 7813$이고 $7813$은 홀수이다.
여분의 $2$가 하나 더 나와 $I_4=2^6\cdot2\cdot7813=2^7\cdot7813$이다.
따라서 $N(4)=7$이다.
(확인: $I_4=1000064$이고 $1000064\div128=7813$.)

$$I_4=2^6(5^6+1)=2^6\cdot15626=2^7\cdot7813,\quad N(4)=7$$

💡 $2$의 더미가 정확히 같은 크기로 만날 때에만 둘을 더하면서 새 $2$가 하나 풀려난다.

#14 극단의 원리 6.EE.A.2 단계 7

최댓값 고르기

세 경우를 비교하자: $k<4$이면 많아야 $N=5$, $k>4$이면 $N=6$, 균형점 $k=4$이면 $N=7$이다.
가장 큰 값은 $7$이고 오직 $k=4$에서만 도달한다.
따라서 $N(k)$의 최댓값은 $\boxed{7}$이며, 이는 선택지 $\textbf{(B)}$이다.

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

💡 정점은 $k$가 극단으로 갈 때가 아니라 두 $2$의 거듭제곱이 딱 맞아떨어지는 경계에 놓인다.

[1] #4 5.NBT.A.2 자릿값을 읽자. 끝 두 자리는 $6$(십의 자리)과 $4$(일의 자리)이므로 고정된 수 $64$를 이룬다. 그 위에 $0$이 $k$개, 다시 그

[2] #4 8.EE.A.1 $2$의 인수는 반드시 두 항 중 하나에서 나오므로 각각 소인수분해하자. $10=2\cdot5$이므로 $10^{k+2}=2^{k+2}\,5^{k

[3] #7 6.NS.B.4 $2^{k+2}5^{k+2}$과 $2^6$을 더할 때 밖으로 뺄 수 있는 $2$는 두 항이 함께 가진 만큼, 즉 두 지수 $k+2$와 $6$ 중

[4] #7 4.OA.B.4 $k+2<6$(즉 $k=1,2,3$)이면 $2^{k+2}$을 빼내어 $I_k=2^{k+2}\big(5^{k+2}+2^{\,4-k}\big)$을

[5] #7 4.OA.B.4 $k+2>6$(즉 $k\ge5$)이면 꼬리 $2^6$이 약한 항이므로 $2^6$을 빼낸다: $I_k=2^6\big(2^{\,k-4}5^{k+2}

[6] #6 6.NS.B.3 남은 유일한 경우는 $k+2=6$, 즉 $k=4$로, 두 항이 모두 정확히 $2^6$을 지닌다: $I_4=2^6\,5^6+2^6=2^6\big(

[7] #14 6.EE.A.2 세 경우를 비교하자: $k<4$이면 많아야 $N=5$, $k>4$이면 $N=6$, 균형점 $k=4$이면 $N=7$이다. 가장 큰 값은 $7$이고

검토

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

대안 접근: 지수 올리기(LTE) 관점을 쓰자. $2^6$을 빼내면 $I_k=2^6\big(2^{\,k-4}5^{k+2}+1\big)$이다($k\ge4$에서 유효하며, 더 작은 $k$는 명백히 $N=k+2\le5$). 괄호는 $k-4=0$, 즉 $k=4$가 아니면 홀수이고, $k=4$일 때 $5^6+1$이 된다. 같은 거듭제곱의 합 규칙으로 $5^6+1$은 $5+1=6$으로 나누어지지만 $2$의 인수는 단 하나뿐이라, $N$은 딱 한 번 $7$까지 오른다. 결론은 같은 $\textbf{(B)}$이다.

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

5.NBT.A.2 0의 개수 패턴과 소수점 위치 설명하기 (자릿값을 따라가며 자릿수 그림 $1\,0\cdots0\,64$를 식 $10^{k+2}+64$로 읽어내기.)
8.EE.A.1 정수 지수의 성질 알고 적용하기 ($10^{k+2}=2^{k+2}5^{k+2}$와 $64=2^6$으로 바꾸고 인수를 뺄 때 지수를 다루기.)
6.NS.B.4 두 수의 최대공약수와 최소공배수 구하기 (두 항의 합에서 공통된 $2$의 거듭제곱, 즉 $2^{k+2}$과 $2^6$ 중 작은 쪽을 밖으로 빼내기.)
4.OA.B.4 약수 쌍 찾고 배수 인식하기; 소수·합성수 판정하기 ($k<4$와 $k>4$ 경우에서 남은 괄호의 홀짝(홀수·짝수)을 판정하기.)
6.NS.B.3 여러 자리 소수의 사칙연산 능숙하게 하기 ($5^6=15625$, 이어 $15626=2\cdot7813$을 계산해 $k=4$에서 여분의 $2$를 뽑아내기.)
6.EE.A.2 문자가 수를 나타내는 식을 쓰고 읽고 계산하기 (세 경우에 걸쳐 $N(k)$를 계산하고 최댓값을 고르기.)

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