AMC 10 · 2021 · #5

학년 7 number-theorycounting

유형 Small-Domain Constrained Search └ 세부 유형 Sum-Target Search

fraction-arithmeticgcdsystematic-enumerationpair-counting systematic-enumerationidentify-subproblems ↑ 선수 지식: fraction-arithmeticgcd

📏 중간 풀이 💡 3 개 인사이트

문제

분자와 분모가 양의 정수이고 그 합이 15인 분수를 특별한 분수라고 부릅니다. 기약분수일 필요는 없습니다. 특별한 분수 두 개를 더하되 같은 것을 두 번 써도 됩니다. 그 합이 정수가 되는 경우를 보고 만들 수 있는 서로 다른 정수가 몇 개인지 세세요.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 빠짐없이 나열하기

특별한 분수는 14개뿐이라 문제의 전체 세계가 한 줄에 들어온다. 전부 나열하는 것은 부담이 적고 짐작할 여지를 없앤다. 하지만 14개를 서로 짝지으면 덧셈이 105번이라 손으로 하기엔 너무 많다. 그래서 나열한 뒤에 기약분수의 분모를 기준으로 다시 정리한다. 이 한 번의 재정리가 거의 모든 쌍을 한꺼번에 걸러내고, 더해 볼 작은 묶음 세 개만 남긴다.

1STEP 1

특별한 분수 모두 나열하기

특별한 분수를 모두 나열합니다.

a + b = 15, a ≥ 1, b ≥ 1 → a/b ∈ { 1/14, 2/13, 3/12, 4/11, 5/10, 6/9, 7/8, 8/7, 9/6, 10/5, 11/4, 12/3, 13/2, 14/1 }

2STEP 2

각각을 기약분수로 만들기

각각을 기약분수로 만듭니다.

1/14, 2/13, 1/4, 4/11, 1/2, 2/3, 7/8, 8/7, 3/2, 2, 11/4, 4, 13/2, 14

3STEP 3

분모가 같아야만 한다

분모가 같아야 합이 정수가 됩니다.

p/q + r/s = n → r/s = (nq - p)/q, gcd(nq - p, q) = gcd(p, q) = 1 → s = q

4STEP 4

분모별로 묶기

분모별로 묶습니다.

q = 1: {2, 4, 14} q = 2: { 1/2, 3/2, 13/2 } q = 4: { 1/4, 11/4 } 2p/q ∈ Z, gcd(p, q) = 1 → q ∣ 2

5STEP 5

묶음 안에서 더하기

묶음 안에서 더합니다.

{2, 4, 14} → {4, 6, 8, 16, 18, 28}, { 1/2, 3/2, 13/2 } → {1, 2, 3, 7, 8, 13}, { 1/4, 11/4 } → {3}

6STEP 6

목록 합쳐서 세기

목록을 합쳐 세면 11개입니다.

{4, 6, 8, 16, 18, 28} ∪ {1, 2, 3, 7, 8, 13} ∪ {3} = {1, 2, 3, 4, 6, 7, 8, 13, 16, 18, 28}, 13 - 2 = 11

정답

최종 집합은 실제 특별한 분수로 하나씩 확인할 수 있다. 1 = 5/10 + 5/10, 3 = 3/12 + 11/4, 7 = 5/10 + 13/2, 28 = 14/1 + 14/1처럼 11개 값 모두 실제로 만들어진다. 묶음별 합의 총 개수는 13인데 이는 정확히 선택지 (E)로, 8과 3이 각각 두 번씩 나온다는 것을 놓친 사람이 빠지는 함정이다. 두 중복 중 하나만 잡으면 12, 선택지 (D)가 된다. 두 중복을 모두 걷어내고 남는 값이 11이므로 앞뒤가 맞는다.

💡핵심 정리

기약분수 두 개는 분모가 이미 같을 때만 정수로 더해지므로, 분모로 묶어 정리하면 엄청나게 많던 쌍이 짧은 목록 세 개로 줄어든다.

특별한 분수 모두 나열하기
각각을 기약분수로 만들기
분모가 같아야만 한다
분모별로 묶기
묶음 안에서 더하기
목록 합쳐서 세기