AMC 10 · 2020 · #21

학년 8 number-theory

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

prime-factorizationlcmgcdfactorialfundamental-counting-principle identify-subproblemscaseworksystematic-enumeration ↑ 선수 지식: prime-factorizationlcm

📏 긴 풀이 💡 3 개 인사이트

문제

5의 배수인 양의 정수 중에서 어떤 조건을 만족하는 것이 몇 개인지 세세요. 조건은 5의 계승과 그 수의 최소공배수가 10의 계승과 그 수의 최대공약수의 다섯 배와 같다는 것입니다.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 작은 문제로 쪼개기

도구 #15(다르게 정리하기): 식 전체를 소인수의 지수로 바꿔 쓴다. lcm이 "큰 쪽 지수 고르기", gcd가 "작은 쪽 지수 고르기"가 되는 순간, 거대한 수에 관한 지저분한 식 하나가 작은 정수에 관한 짧은 식 몇 개로 바뀐다. 도구 #4(변수 도입하기): n의 지수를 a, b, c, d로 이름 붙인다. 도구 #7(작은 문제로 쪼개기): 서로 다른 소수는 절대 간섭하지 않으므로 각 소수가 독립적인 작은 문제가 되고, 그 개수들을 곱하면 된다. 도구 #2(빠짐없이 나열하기): 각 소수마다 살아남는 지수 값을 정확히 나열한다.

1STEP 1

두 계승 소인수분해

두 계승을 소인수로 씁니다.

5! = 2³ · 3¹ · 5¹, 10! = 2⁸ · 3⁴ · 5² · 7¹

2STEP 2

쓸 수 있는 소수 정하기

다른 소수는 들어갈 수 없습니다.

n = 2^a · 3^b · 5^c · 7^d

3STEP 3

식을 지수로 바꾸기

최소공배수와 최대공약수를 지수로 씁니다.

max(3, a) = min(8, a), max(1, b) = min(4, b), max(1, c) = min(2, c) + 1, max(0, d) = min(1, d)

4STEP 4

소수 2의 식 풀기

범위 하나가 나옵니다.

3 ≤ a ≤ 8 → a ∈ {3, 4, 5, 6, 7, 8}, 6가지

5STEP 5

소수 3과 7의 식 풀기

두 소수도 같은 방식입니다.

b ∈ {1, 2, 3, 4}, 4가지; d ∈ {0, 1}, 2가지

6STEP 6

소수 5의 식 풀기

5의 지수는 하나로 정해집니다.

c = 3, 1가지

7STEP 7

경우의 수 곱하기

곱하면 48입니다.

6 · 4 · 1 · 2 = 48 → (D)

정답

가장 작은 해 (a, b, c, d) = (3, 1, 3, 0), 즉 n = 8 · 3 · 125 = 3000을 확인해 본다. lcm(120, 3000) = 3000이고 gcd(3628800, 3000) = 600이며 5 · 600 = 3000이므로 성립한다. 가장 큰 해 (8, 4, 3, 1)도 확인하면 n = 256 · 81 · 125 · 7 = 18144000, lcm(120, n) = n, gcd(10!, n) = 2⁸ · 3⁴ · 5² · 7 = 3628800, 5 · 3628800 = 18144000으로 성립한다. 48 = 6 · 4 · 1 · 2라는 구조는 함정 선택지와도 맞아떨어진다. 소수 7이 두 가지를 준다는 사실을 잊으면 절반인 (B) 24가 되고, a를 8까지 가지 않고 5에서 멈춰도 3 · 4 · 1 · 2 = 24가 된다. "5의 배수"라는 조건은 장식이 아니다. 이 조건을 빼면 c = 0이 허용되어 답이 96으로 두 배가 되는데, 이는 선택지에 아예 없다.

💡핵심 정리

모든 것을 소인수의 지수로 바꿔 쓰면, lcm은 큰 지수를 gcd는 작은 지수를 고르므로 거대한 식 하나가 소수마다 하나씩인 작은 식으로 쪼개진다. 2는 6가지, 3은 4가지, 5는 1가지, 7은 2가지이므로 6 · 4 · 1 · 2 = 48이다.

두 계승을 소인수분해하기
n이 쓸 수 있는 소수 확정하기
식을 지수 식으로 바꾸기
소수 2의 식 풀기
소수 3과 소수 7의 식 풀기
소수 5의 식 풀기
독립적인 경우의 수 곱하기