AMC 10 · 2021 · #25

학년 11 number-theory

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

divisor-countprime-factorizationoptimizationexponents identify-subproblemsextreme-principle ↑ 선수 지식: divisor-count

📏 긴 풀이 💡 3 개 인사이트

문제

양의 정수마다 그 수의 약수의 개수를 세제곱근으로 나눈 값을 봅니다. 정확히 하나의 양의 정수에서 이 값이 다른 모든 정수에서보다 엄격히 큽니다. 그 정수의 자릿수를 모두 더하세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 작은 문제로 쪼개기

모든 양의 정수를 정면으로 뒤지는 것은 불가능하므로, 풀이 전체가 도구 #7(작은 문제로 쪼개기)에 기댄다. f를 소수마다 하나씩의 인수를 갖는 곱으로 바꿔 쓰고 서로 다른 소수의 지수를 독립적으로 고를 수 있다는 점을 확인하면, 하나의 거대한 최대화 문제가 소수마다의 작은 최대화 문제로 갈라진다. 도구 #4(변수 도입하기)는 소인수분해의 지수를 a₁,a₂,…로 이름 붙여 그 준비를 한다. 도구 #15(다르게 정리하기)는 바로 그 바꿔 쓰기 자체로, d(n)/∛(n)을 "개수 나누기 근호"에서 "소수별 조각들의 곱"으로 재편성한다. 도구 #14(극단의 원리)는 "봉우리가 어디인가"라는 물음을 이웃한 지수끼리의 비교로 바꾸고, 그 비교를 세제곱하면 순수한 정수 계산이 된다. 이어 도구 #6(추측하고 확인하기)으로 p=2,3,5,7에 그 값싼 판정을 돌리고, 도구 #3(가능성 지우기)으로 11 이상의 모든 소수를 한 번에 날린다.

1STEP 1

약수의 개수 세기

약수의 개수를 지수로 씁니다.

n=p₁^a₁p₂^a₂… p_k^a_k ⟹ d(n)=(a₁+1)(a₂+1)…(a_k+1)

2STEP 2

소수별 인수로 쪼개기

값이 소수마다 쪼개집니다.

f(n)=d(n)/∛(n)=a₁+1{p₁^a₁/3}·a₂+1{p₂^a₂/3}…a_k+1{p_k^a_k/3}=Π_i=1^kg_p_i(a_i), g_p(a)=a+1{p^a/3}

3STEP 3

소수마다 따로 최대화

소수마다 따로 최대로 만듭니다.

f(n)=Π_p 소수 g_p(a_p) (각 a_p 는 자유), g_p(0)=1

4STEP 4

하나 더 넣을지 판정하기

지수를 하나 늘리는 것이 이득인지 봅니다.

(g_p(a+1))/g_p(a)=a+2{(a+1) p¹/3} ＞ 1 ⇔ (a+2)³ ＞ p(a+1)³

5STEP 5

작은 소수에 적용하기

작은 소수마다 최적 지수를 구합니다.

p=2: a=3; p=3: a=2; p=5: a=1; p=7: a=1

6STEP 6

큰 소수 버리고 곱하기

곱해서 자릿수를 더하면 9입니다.

N=2³·3²·5¹·7¹=2520, 2+5+2+0=9 → (E)

정답

N=2520을 가장 가까운 경쟁자들과 견줘 보자. d(2520)=4·3·2·2=48이고 ∛(2520)≈13.61이므로 f(2520)≈3.53이다. 두 배인 5040=2⁴·3²·5·7은 d=60, ∛(5040)≈17.14이므로 f≈3.50으로 더 작고, 이는 2의 지수가 3에서 멈춰야 한다는 결론과 맞아떨어진다. 절반인 1260=2²·3²·5·7은 d=36, ∛(1260)≈10.80이므로 f≈3.33으로 역시 더 작다. 다음 소수를 붙인 27720=2520·11은 d=96, ∛(27720)≈30.26이므로 f≈3.17로 확실히 나쁘다. 선택지 자체에서 나오는 독립적인 확인도 있다. 3²이 N을 나누므로 9가 N을 나누고, 따라서 N의 자리 숫자 합은 9의 배수여야 한다. 5,6,7,8,9 중 이 조건을 만족하는 것은 9뿐이다. 또한 2520은 lcm(1,2,…,10)으로도 알려진 수이며, 이런 형태의 문제에서 이겨야 마땅한 약수 풍부한 값이다.

💡핵심 정리

함수를 소수마다 하나씩의 조각으로 쪼갠 뒤 각 소수에게 "하나 더 넣을 만한가?"를 물으면, 답은 2³·3²·5·7=2520에서 멈추고 그 자리 숫자의 합은 9이다.

지수에서 약수의 개수 세기
f를 소수별 인수로 쪼개기
소수마다 따로 최대로 만들기
한 개 더 넣는 것이 이득인지 판정하기
작은 소수들에 판정 돌리기
큰 소수를 버리고 곱하기