AMC 10 · 2016 · #22

학년 7 number-theory

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

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

📏 긴 풀이 💡 4 개 인사이트

문제

세 미지수의 두 개씩의 최소공배수가 주어져 있다. 순서 있는 세 쌍의 수를 세어라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 작은 문제로 쪼개기

정수에 대한 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²

2STEP 2

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

각 조건은 지수의 최댓값이다.

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

3STEP 3

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; (e_x,e_z)∈{(1,0),(0,1),(1,1)}→ 3

5STEP 5

5의 거듭제곱 세기

마지막은 완전히 정해진다.

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

6STEP 6

독립된 개수들을 곱하기

곱하면 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의 거듭제곱 세기
독립된 개수들을 곱하기