AMC 10 · 2013 · #9

학년 8 number-theory

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

factoriallegendre-formulaprime-factorizationperfect-squaresexponents extremal-constructionconvert-to-algebra ↑ 선수 지식: prime-factorizationfactorial

📏 긴 풀이 💡 3 개 인사이트

문제

계승의 가장 큰 제곱수 약수를 잡아 그 제곱근을 살핀다. 제곱근의 소인수 지수를 더하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 극단의 원리

12!은 아홉 자리 수여서 가장 큰 제곱 약수를 하나씩 시험해 찾는 것은 불가능하다. 좌표를 바꾸자. 모든 약수를 소인수의 지수 목록으로 나타낸다. 이 좌표에서 12!을 나눈다는 것은 '각 지수가 충분히 작다'는 뜻이고 완전제곱수라는 것은 '각 지수가 짝수다'라는 뜻이라, 두 조건은 서로 부딪치지 않는다. 그래서 소수마다 따로따로 지수를 최대로 밀어 올릴 수 있고, 따로 얻은 최댓값들을 합치면 모든 경쟁자를 한꺼번에 이기는 하나의 수가 된다. 마지막은 계산 정리다. 제곱근을 위해 지수를 반으로 줄이고 더하면 된다.

1STEP 1

지수 좌표로 바꾸기

지수 좌표가 모든 약수를 설명한다.

12! = 2^e₂ · 3^e₃ · 5^e₅ · 7^e₇ · 11^e₁₁, d = 2^a₂ · 3^a₃ · 5^a₅ · 7^a₇ · 11^a₁₁

2STEP 2

배수를 세어 각 소수의 지수 구하기

배수를 세면 각 소수의 지수가 나온다.

e₂=⌊12/2⌋+⌊12/4⌋+⌊12/8⌋=6+3+1=10, e₃=⌊12/3⌋+⌊12/9⌋=4+1=5, e₅=2, e₇=1, e₁₁=1

3STEP 3

두 조건을 지수 규칙으로 쓰기

두 조건이 단순한 지수 규칙이 된다.

d ∣ 12! ⇔ a_p ≤ e_p for every p; d = m² ⇔ a_p is even for every p

4STEP 4

소수마다 최대로 밀어 올리기

각 소수를 자기 최대까지 민다.

N = 2¹⁰ · 3⁴ · 5² = (2⁵ · 3² · 5)² = 1440² = 2073600

5STEP 5

N을 이길 수 없음을 보이기

다른 어떤 것도 그것을 이길 수 없다.

a_p even and a_p ≤ e_p ⟹ a_p ≤ 2⌊e_p/2⌋ ⟹ d ∣ N ⟹ d ≤ N

6STEP 6

제곱을 거꾸로 풀기

제곱근을 취하면 모든 지수가 절반이 된다.

√(N) = √(2¹⁰ · 3⁴ · 5²) = 2⁵ · 3² · 5¹ = 1440

7STEP 7

지수 더하기

더하면 8, 보기 (B).

5 + 2 + 1 = 8

정답

수를 직접 확인한다. 소수 세기 결과는 12! = 2¹0 * 3⁵ * 5² * 7 * 11인데, 이를 곱하면 1024 * 243 * 25 * 77 = 479001600으로 12!과 같으므로 지수가 맞다. 다음으로 1440² = 2073600이고 479001600 / 2073600 = 231 = 3 * 7 * 11이다. 이 나머지 부분은 같은 소수가 두 번 나오지 않는 수라서 더 뽑아낼 제곱 인수가 남아 있지 않다. 즉 제곱 부분을 끝까지 뽑아냈다는 뜻이다. 마지막으로 sqrt(2073600) = 1440 = 2⁵ * 3² * 5¹의 지수 합은 5 + 2 + 1 = 8이고 이는 보기 (C)다. 크기도 자연스럽다. 답은 12! 자체의 지수 합인 10 + 5 + 2 + 1 + 1 = 19보다 작아야 하고 대략 그 절반이어야 하므로, 8은 제자리에 있고 12는 너무 크다.

💡핵심 정리

수를 소인수의 지수로 나타내면 '가장 큰 제곱 약수'는 각 지수를 허용되는 가장 큰 짝수로 만드는 일일 뿐이다.

지수 좌표로 바꾸기
배수를 세어 각 소수의 지수 구하기
두 조건을 지수 규칙으로 쓰기
소수마다 최대로 밀어 올리기
N을 이길 수 없음을 보이기
제곱을 거꾸로 풀기
지수 더하기