AMC 10 · 2016 · #25

학년 7 number-theory

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

lcmprime-factorizationexponents casework ↑ 선수 지식: lcmprime-factorization

📏 긴 풀이 💡 4 개 인사이트

문제

lcm(x,y)=72, lcm(x,z)=600, lcm(y,z)=900을 모두 만족하는 양의 정수 순서쌍 (x,y,z)의 개수를 구하라. 순서쌍이므로 (x,y,z)의 순서를 바꾼 것은 서로 다른 경우로 센다.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 작은 문제로 쪼개기

정수에 대한 lcm 조건은 사실 하나처럼 보이지만 소수별로 따로 작동한다. 결과에서 2의 지수는 입력들의 2 지수만으로 정해지고, 3과 5도 마찬가지다. 그래서 도구 #7(작은 문제로 쪼개기)로 어려운 세기를 세 개의 독립된 소수 문제로 나눈다. 도구 #4(변수 도입하기)로 각 소수의 지수를 x, y, z에서 변수로 두면 각 lcm은 '두 지수 중 큰 값이 이것과 같다'는 깔끔한 조건이 된다. 각 소수마다 가능한 지수는 아주 작은 집합이라 도구 #2(빠짐없이 나열하기)로 유효한 지수 순서쌍을 직접 센다. 소수들은 독립적으로 고르므로 세 개수를 곱한다.

1STEP 1

세 목표값을 소인수분해

각 목표를 소인수분해: 72=2³·3², 600=2³·3·5², 900=2²·3²·5². 등장하는 소수는 2, 3, 5뿐이다.

72 = 2³· 3², 600 = 2³· 3¹· 5², 900 = 2²· 3²· 5²

2STEP 2

각 lcm을 지수의 최댓값으로 바꾸기

각 소수의 지수를 x,y,z에 두면, lcm 지수는 두 입력 중 큰 값이라 소수 2,3,5를 따로 푼다.

각 소수마다 max(e_x,e_y), max(e_x,e_z), max(e_y,e_z)가 목표 지수와 같아야 한다

3STEP 3

2의 거듭제곱 세기

소수 2: e_x=3 강제, 둘 다 ≤2인 max(e_y,e_z)=2를 주는 순서쌍은 5가지.

e_x=3; (e_y,e_z)∈{(2,0),(2,1),(2,2),(1,2),(0,2)}→ 5

4STEP 4

3의 거듭제곱 세기

소수 3: e_y=2 강제, 둘 다 ≤1인 max(e_x,e_z)=1을 주는 순서쌍은 3가지.

e_y=2; (e_x,e_z)∈{(1,0),(0,1),(1,1)}→ 3

5STEP 5

5의 거듭제곱 세기

소수 5: max(e_x,e_y)=0이 e_x=e_y=0을 강제하고 e_z=2 — 모두 고정되어 정확히 1가지.

e_x=0, e_y=0, e_z=2→ 1

6STEP 6

독립된 개수들을 곱하기

세 소수의 선택은 독립이므로 곱의 법칙으로 전체는 5×3×1=15 — 답은 (A).

5× 3× 1 = 15 → (A)

정답

곱 5×3×1=15는 정확히 보기 (A)에 떨어지고, 모든 지수 조합(2의 거듭제곱 0부터 3, 3과 5의 거듭제곱 0부터 2)을 훑어 확인하면 정확히 15개의 순서쌍이 세 lcm 조건을 모두 만족한다. 조건이 빡빡해서 모든 소수에서 한 변수가 최댓값으로 고정되었고, 그래서 개수가 27이나 64 같은 큰 보기로 불어나지 않았다.

💡핵심 정리

lcm은 각 소수에서 더 큰 지수만 택하므로, 문제를 소수별 퍼즐로 쪼개 5, 3, 1가지를 센 뒤 곱하면 15가 된다.

세 목표값을 소인수분해
각 lcm을 지수의 최댓값으로 바꾸기
2의 거듭제곱 세기
3의 거듭제곱 세기
5의 거듭제곱 세기
독립된 개수들을 곱하기