AMC 10 · 2007 · #24

학년 6 number-theory

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

gcddivisibility-rulescasework casework ↑ 선수 지식: gcd

📏 긴 풀이 💡 4 개 인사이트

문제

양의 정수 두 개가 1보다 큰 공약수를 갖지 않으면서 어떤 분수의 합을 정수로 만든다. 그런 쌍의 개수를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

infinitely many

풀이 과정

전략 작은 문제로 쪼개기

두 개의 분수를 따로 두면 판단하기 어렵다. 먼저 하나의 분수 (9a²+14b²)/9ab로 합치면 "정수이다"라는 조건은 그저 분모가 분자를 나눈다는 뜻이 된다. Tool #7 (작은 문제로 쪼개기)로 이 한 개의 나눗셈 조건을 작은 조각으로 나눈다: a는 무엇을 나눠야 하는가, b는 무엇을 나눠야 하는가, 그리고 공통인수 3은 어떻게 작동하는가. 서로소 조건 덕분에 각 조각이 짧은 약수 목록으로 바뀌어 a와 b가 가질 수 있는 값이 몇 개로 줄어든다. 그다음 Tool #2 (빠짐없이 나열하기)로 그 후보들을 확인하고, Tool #3 (가능성 지우기)로 실패하는 경우를 버리면 정확한 개수가 남는다.

1STEP 1

하나의 분수로 합치기

합치면 정수로 만들 분수 하나가 된다.

a/b+14b/9a=9a²/9ab+14b²/9ab=(9a²+14b²)/9ab

2STEP 2

a가 나눠야 하는 것

첫 수가 작은 상수를 나눠야 한다.

a ∣ 9a²+14b² → a ∣ 14b² → a ∣ 14 → a ∈ {1,2,7,14}

3STEP 3

b가 나눠야 하는 것

둘째도 마찬가지라 또 다른 짧은 목록이 나온다.

b ∣ 9a²+14b² → b ∣ 9a² → b ∣ 9 → b ∈ {1,3,9}

4STEP 4

짧은 후보 목록으로 좁히기

둘을 합치면 후보가 몇 개만 남는다.

a ∈ {1,2,7,14}, b ∈ {1,3,9}

5STEP 5

각 b 값 확인하기

둘째 값을 하나씩 시험하면 하나만 남는다.

b=1: 9a ∣ 14 (불가); b=9: 9 ∤ a²+126; b=3: (a²+14)/3a (항상 성립)

6STEP 6

살아남은 쌍 세기

남은 것을 세면 4, 보기 (A).

(1,3),(2,3),(7,3),(14,3) → 4 쌍 → (A)

정답

네 쌍을 각각 다시 대입했더니 정수 5, 3, 3, 5가 나와 넷 모두 실제로 성립한다. 어떤 쌍도 중복해서 세지 않았고, b 에 대한 경우 분석이 b=1과 b=9는 아무것도 주지 않음을 증명했으므로 빠뜨린 것도 없다 — 이는 (E) 무수히 많다와 더 큰 개수인 (B) 6, (C) 9, (D) 12를 배제한다. 정확히 4 개의 쌍이 남아 (A)와 일치한다.

💡핵심 정리

분수를 하나로 붙인 뒤, 공약수가 없다는 규칙이 각 문자를 짧은 약수 목록으로 몰아넣게 하면, 그다음엔 확인할 경우가 몇 개밖에 남지 않는다.

하나의 분수로 합치기
a가 나눠야 하는 것
b가 나눠야 하는 것
짧은 후보 목록으로 좁히기
각 b 값 확인하기
살아남은 쌍 세기