AMC 10 · 2019 · #19

학년 6 arithmetic

유형 Overlap / Complement Counting └ 세부 유형 Complement by Subtracting Forbidden Arrangements

divisor-countprime-factorizationcombinatorial-identityexponents complementary-countingidentify-subproblems ↑ 선수 지식: divisor-countprime-factorization

📏 긴 풀이 💡 4 개 인사이트

문제

Let $S$ be the set of all positive integer divisors of $100,000.$ How many numbers are the product of two distinct elements of $S?$

답을 골라 클릭하세요.

(A)

(B)

100

(C)

117

(D)

119

(E)

121

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $S$ 를 $100{,}000$ 의 모든 양의 약수의 집합이라 하자. $S$ 의 서로 다른 두 원소의 곱으로 표현되는 서로 다른 수는 모두 몇 개인가?

주어진 것: $100{,}000 = 10^5 = 2^5 \cdot 5^5$; $S$ = $100{,}000$ 의 양의 약수 집합; 각 약수는 $2^a \cdot 5^b$ ($0 \le a \le 5$, $0 \le b \le 5$) 형태; $|S| = 6 \cdot 6 = 36$; 선택지: (A) $98$, (B) $100$, (C) $117$, (D) $119$, (E) $121$

구하는 것: $d_1 \cdot d_2$ ($d_1, d_2 \in S$, $d_1 \ne d_2$) 의 서로 다른 값의 개수

이해

문제 재정리: $S$ 를 $100{,}000$ 의 모든 양의 약수의 집합이라 하자. $S$ 의 서로 다른 두 원소의 곱으로 표현되는 서로 다른 수는 모두 몇 개인가?

계획

주요 도구: #16 관점 바꾸기

보조 도구: #7 작은 문제로 쪼개기, #9 더 쉬운 문제로 줄이기

도구 #16 (관점 바꾸기): 모든 후보 값($10^{10}$ 의 약수 $11 \cdot 11 = 121$ 개)을 나열한 후 서로 다른 두 약수의 곱으로 표현 불가능한 것을 빼기. 도구 #7 (쪼개기): 곱은 $2^a \cdot 5^b$ 형태이므로 "어떤 $(a, b)$ 쌍이 도달 가능한가" 로 문제 분할. 도구 #9 (더 쉬운 문제): $100 = 2^2 \cdot 5^2$ 같은 작은 경우로 먼저 확인.

실행 — 정답: C

#7 작은 문제로 쪼개기 6.NS.B.4 단계 1

후보 집합 설정.
$S$ 의 원소는 $2^a \cdot 5^b$ ($0 \le a, b \le 5$).
두 원소의 곱은 $a_1 + a_2 \in [0, 10]$, $b_1 + b_2 \in [0, 10]$.
따라서 모든 곱은 $2^{10} \cdot 5^{10}$ 의 약수 — $(10+1)(10+1) = 121$ 개의 후보.

$$\text{후보} = 11 \cdot 11 = 121$$

💡 곱은 $(a, b)$ 합의 $11 \times 11$ 격자 — 전체 격자에서 시작.

#9 더 쉬운 문제로 줄이기 6.EE.B.6 단계 2

어떤 후보가 서로 다른 두 약수에서 만들 수 없는지 확인.
값 $2^A \cdot 5^B$ 는 서로 다른 $(a_1, b_1) \ne (a_2, b_2)$ 와 $a_1 + a_2 = A$, $b_1 + b_2 = B$, $0 \le a_i, b_i \le 5$ 을 필요로 함.

$$a_1 + a_2 = A,\;\; b_1 + b_2 = B,\;\; 0 \le a_i, b_i \le 5,\;\; (a_1,b_1) \ne (a_2,b_2)$$

💡 "서로 다른 약수" 를 "서로 다른 $(a, b)$ 점" 으로 번역.

#16 관점 바꾸기 6.EE.B.6 단계 3

$A = B = 0$ 즉 후보 $1$ 검사: $a_1 + a_2 = 0$, $b_1 + b_2 = 0$ 은 $a_i, b_i \ge 0$ 이므로 모두 $0$ 으로 강제.
두 약수 모두 $1$ — 서로 다르지 않음.
불가능.

$$2^0 \cdot 5^0 = 1 \;\;\text{(불가능 — } (0,0) \cdot (0,0) \text{로 강제)}$$

💡 $1$ 을 만드는 유일한 방법은 $1 \times 1$ — 같은 약수 두 번.

#16 관점 바꾸기 6.EE.B.6 단계 4

$A = 10, B = 10$, 후보 $2^{10} \cdot 5^{10} = 10^{10}$ 검사: $a_i \le 5$ 이므로 $a_1 = a_2 = 5$ 강제, $b_1 = b_2 = 5$ 강제.
두 약수 모두 $2^5 \cdot 5^5 = 100{,}000$ — 서로 다르지 않음.
불가능.

$$2^{10} \cdot 5^{10} \;\;\text{(불가능 — 둘 다 } 10^5\text{)}$$

💡 격자 최상단 모서리도 같은 함정 — 강제 쌍.

#16 관점 바꾸기 6.EE.B.6 단계 5

$A = 10, B = 0$, 후보 $2^{10}$ 검사: $a_1 = a_2 = 5$, $b_1 = b_2 = 0$ 강제.
두 약수 모두 $32$ — 불가능.

$$2^{10} \;\;\text{(불가능 — 둘 다 } 32\text{)}$$

💡 $2$ 축의 같은 강제 쌍 함정.

#16 관점 바꾸기 6.EE.B.6 단계 6

$A = 0, B = 10$, 후보 $5^{10}$ 검사: 마찬가지로 강제 쌍 — 둘 다 $5^5 = 3125$.
불가능.

$$5^{10} \;\;\text{(불가능 — 둘 다 } 3125\text{)}$$

💡 앞 경우의 대칭.

#9 더 쉬운 문제로 줄이기 6.EE.B.6 단계 7

나머지 모든 후보는 가능 확인.
네 모서리 외의 $(A, B) \in [0, 10]^2$ 에는 항상 서로 다른 두 점 쌍이 있음.
예: $(A, B) = (1, 0)$ 은 $(0,0), (1,0)$.
$(A, B) = (5, 5)$ 은 $(0,0), (5,5)$.
$(A, B) = (10, 5)$ 은 $a$ 축에서 $5,5$ 강제이지만 $b$ 축에서 $b_1 = 0, b_2 = 5$ 가능 — $(5,0)$ 과 $(5,5)$ 서로 다름.
강제 쌍 함정은 두 좌표 모두 단 하나의 분해만 허용할 때 (네 모서리) 만 발생.

$$\text{불가능} = \{(0,0), (10,0), (0,10), (10,10)\},\;\; |\text{불가능}| = 4$$

💡 두 좌표 모두에서 분해가 유일 — 네 극단 모서리에서만 발생.

#16 관점 바꾸기 4.OA.A.3 단계 8

빼기: 가능 수 $= 121 - 4 = 117$.
답은 (C).

$$121 - 4 = \boxed{117}$$

💡 전체 - 예외 — 끝.

[1] #7 6.NS.B.4 후보 집합 설정. $S$ 의 원소는 $2^a \cdot 5^b$ ($0 \le a, b \le 5$). 두 원소의 곱은 $a_1 + a_2 \i

[2] #9 6.EE.B.6 어떤 후보가 서로 다른 두 약수에서 만들 수 없는지 확인. 값 $2^A \cdot 5^B$ 는 서로 다른 $(a_1, b_1) \ne (a_2,

[3] #16 6.EE.B.6 $A = B = 0$ 즉 후보 $1$ 검사: $a_1 + a_2 = 0$, $b_1 + b_2 = 0$ 은 $a_i, b_i \ge 0$ 이므로

[4] #16 6.EE.B.6 $A = 10, B = 10$, 후보 $2^{10} \cdot 5^{10} = 10^{10}$ 검사: $a_i \le 5$ 이므로 $a_1 =

[5] #16 6.EE.B.6 $A = 10, B = 0$, 후보 $2^{10}$ 검사: $a_1 = a_2 = 5$, $b_1 = b_2 = 0$ 강제. 두 약수 모두 $3

[6] #16 6.EE.B.6 $A = 0, B = 10$, 후보 $5^{10}$ 검사: 마찬가지로 강제 쌍 — 둘 다 $5^5 = 3125$. 불가능.

[7] #9 6.EE.B.6 나머지 모든 후보는 가능 확인. 네 모서리 외의 $(A, B) \in [0, 10]^2$ 에는 항상 서로 다른 두 점 쌍이 있음. 예: $(A,

[8] #16 4.OA.A.3 빼기: 가능 수 $= 121 - 4 = 117$. 답은 (C).

검토

합리성 확인: $117$ 은 선택지 $100$ 과 $119$ 사이, 정확히 $121 - 4$. $121$ 은 $100{,}000^2$ 의 약수 개수, $4$ 는 쌍둥이 분해만 가능한 모서리 개수. 작은 경우 확인: $100 = 2^2 \cdot 5^2$ 의 경우 — 약수 $9$ 개, 후보 $(2 \cdot 2 + 1)^2 = 25$, 같은 4 모서리 — 답 $21$ (직접 나열과 일치).

대안 접근: 도구 #2 (나열): 각 후보 $(A, B)$ 마다 분해 수를 셀 수 있지만 대부분 여러 개 — 적어도 하나면 충분하므로 모서리 예외 계산이 가장 깔끔. 보완법 없는 직접 나열은 훨씬 느림.

사용된 CCSS 표준 (최저 학년 6)

4.OA.A.3 사칙연산으로 다단계 문장제 풀이 (최종 뺄셈 $121 - 4 = 117$.)
6.NS.B.4 두 수의 최대공약수·최소공배수 찾기 (소인수분해 사용) (소인수분해 $100{,}000 = 2^5 \cdot 5^5$ 과 약수 개수 $(5+1)(5+1)$ 계산.)
6.EE.B.6 변수를 사용해 식 작성·문제 해결 (약수를 $2^a \cdot 5^b$ 로 표현하고 "어떤 $(A, B)$ 가 서로 다른 $(a_i, b_i)$ 쌍으로 도달 가능한가" 로 환원.)

⭐ 이 AMC 10 문제는 6학년 때 배운 소인수분해만 알면 풀 수 있어요 — $10^5$ 의 모든 약수는 $2^a \cdot 5^b$ 이므로 곱은 $10^{10}$ 의 약수 $121$ 개 중 하나, 네 "모서리" 만 서로 다른 쌍 조건 불충족. $121 - 4 = 117$. 답은 $\textbf{(C)}$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: C

검토

사용된 CCSS 표준 (최저 학년 6)

비슷한 유형 더 풀어보기