AMC 10 · 2016 · #24

학년 9 number-theory
유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint
gcdlcmprime-factorizationp-adic-valuation identify-subproblemscomplementary-counting ↑ 선수 지식: gcdlcm
📏 긴 풀이 💡 4 개 인사이트
문제
최대공약수와 최소공배수가 정해진 네 쌍의 개수를 센다. 목표 개수를 주는 가장 작은 값을 구하여라.

답을 골라 클릭하세요.

(A)
13,860
(B)
20,790
(C)
21,560
(D)
27,720
(E)
41,580
풀이 과정
전략 작은 문제로 쪼개기

이 문제의 두 조건은 모두 나누어떨어짐에 관한 것이고, 나누어떨어짐은 소수마다 따로 결정된다: 최대공약수에서 소수 p 의 지수는 네 지수 중 최솟값이고, 최소공배수에서는 최댓값이다. 그래서 도구 #7 (작은 문제로 쪼개기)이 전체를 이끈다 — 소수 하나가 독립된 세기 문제 하나가 되고, 서로 다른 소수를 엮는 조건이 하나도 없으므로 각 답이 곱해진다. 먼저 도구 #9 (더 쉬운 문제로 줄이기)로 공통인수 77을 떼어내 최대공약수 조건을 더 깔끔한 '최대공약수가 1' 로 바꾼다. 도구 #4 (변수 도입하기)로 지수에 이름을 붙이면 '최대공약수'와 '최소공배수'가 '최솟값'과 '최댓값'으로 바뀐다. 도구 #16 (관점 바꾸기)으로 각 소수의 쌍을 직접 만들지 않고, 최댓값을 놓치거나 최솟값을 놓친 것들을 빼는 방식으로 센다. 그다음 문제가 뒤집힌다: 개수 77,000은 알고 지수는 모르므로, 도구 #3 (가능성 지우기)과 도구 #2 (빠짐없이 나열하기)로 77,000을 인수분해해 지수 조합을 하나만 남긴다. 마지막으로 도구 #14 (극단의 원리)로 그 지수들을 어떤 소수에 어떻게 배치해야 가장 작아지는지 정한다.

1STEP 1

공통인수 77을 떼어내기

공통 인수를 떼면 두 조건이 단순해진다.

a=77A, b=77B, c=77C, d=77D ⟹ gcd(a,b,c,d)=77gcd(A,B,C,D), lcm(a,b,c,d)=77lcm(A,B,C,D)
2STEP 2

소수 하나씩 따로 보기

각 소수를 따로 다룰 수 있다.

gcd(A,B,C,D)=1 ⇔ min(α_p,β_p,γ_p,δ_p)=0 (모든 p) ; lcm(A,B,C,D)=N ⇔ max(α_p,β_p,γ_p,δ_p)=k_p (모든 p)
3STEP 3

개수는 소수마다 인수 하나

따라서 개수는 소수마다의 곱이다.

77000=Π_p ∣ N f(k_p), f(k)=#{(m₁,m₂,m₃,m₄)∈{0,1,…,k}⁴ : max_i m_i=k, min_i m_i=0}
4STEP 4

여집합으로 소수별 개수 세기

여집합 세기가 각 인수를 준다.

f(k)=(k+1)⁴-2k⁴+(k-1)⁴=12k²+2 (k ≥ 1); f(1)=14, f(2)=50, f(3)=110, f(4)=194, f(5)=302
5STEP 5

모든 인수는 2 곱하기 홀수

모든 인수는 홀수의 두 배다.

f(k)=2(6k²+1), 6k²+1은 홀수; 77000=2³ · 5³ · 7 · 11 ⟹ r=3, Π_i=1³(6k_i²+1)=9625
6STEP 6

세 지수를 확정하기

그것이 지수를 세 값으로 못박는다.

6k²+1∈{7,25,55,385} (k=1,2,3,8); 7 · 25 · 55=9625 만이 세 인수의 곱 ⟹ {k₁,k₂,k₃}={1,2,3}
7STEP 7

N 을 가장 작게 만들기

가장 작은 소수에 가장 큰 지수를 준다.

N=q₁³q₂²q₃¹ (q₁ ＜ q₂ ＜ q₃) ≥ 2³ · 3² · 5=360
8STEP 8

77을 다시 곱하기

다시 곱하면 27720, 보기 (A).

n=77N=77 · 360=27720=2³ · 3² · 5 · 7 · 11, f(3)f(2)f(1)=110 · 50 · 14=77000
정답
27,720
인쇄된 선택지를 모두 기계에 넣어 본다. 77로 나누고 소인수분해한 뒤 f(1)=14, f(2)=50, f(3)=110을 곱하면 된다. (A) 13,860=77 · 180이고 180=2² · 3² · 5 이므로 50 · 50 · 14=35,000. (B) 20,790=77 · 270이고 270=2 · 3³ · 5 이므로 14 · 110 · 14=21,560. (C) 21,560=77 · 280이고 280=2³ · 5 · 7 이므로 110 · 14 · 14=21,560. (D) 27,720=77 · 360이고 360=2³ · 3² · 5 이므로 110 · 50 · 14=77,000. (E) 41,580=77 · 540이고 540=2² · 3³ · 5 이므로 50 · 110 · 14=77,000. 두 선택지가 77,000에 도달하며 그중 (D)가 더 작다 — 이것이 바로 문제가 요구하는 값이고, 동시에 '조건을 만족하는 n 을 하나 찾는 것'과 '가장 작은 n 을 찾는 것'이 다르다는 경고이기도 하다. 공식 자체도 k=1 에서 손으로 확인된다: 0과 1 로만 이루어지고 둘 다 쓰는 네 쌍은 2⁴-2=14 개이고, f(1)=12+2=14와 일치한다.
💡핵심 정리

최대공약수와 최소공배수는 언제나 소수 하나씩 지수만 비교하므로, 77,000 같은 개수는 소수마다 인수 하나로 쪼개진다 — 개수를 인수분해하면 답의 지수가 그대로 떨어져 나온다.

  • 공통인수 77을 떼어내기
  • 소수 하나씩 따로 보기
  • 개수는 소수마다 인수 하나
  • 여집합으로 소수별 개수 세기
  • 모든 인수는 2 곱하기 홀수
  • 세 지수를 확정하기
  • N 을 가장 작게 만들기
  • 77을 다시 곱하기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.