AMC 10 · 2013 · #24

학년 6 number-theory

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

divisor-sumdivisor-countprime-factorization caseworksystematic-enumeration ↑ 선수 지식: prime-factorizationdivisor-count

📏 긴 풀이 💡 3 개 인사이트

문제

양의 정수 $n$ 이 '좋은 수'라는 것은, 양의 약수가 정확히 네 개( $1$ 과 $m$ 포함)인 양의 정수 $m$ 이 존재하여 그 네 약수의 합이 $n$ 과 같은 경우를 말한다. 집합 $\{ 2010,2011,2012,\dotsc,2019 \}$ 에 속한 수 중 '좋은 수'는 몇 개인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 양의 정수 $m$ 이 정확히 네 개의 양의 약수($1$ 과 $m$ 포함)를 가지고 그 네 약수의 합이 $n$ 이 되는 $m$ 이 존재하면 양의 정수 $n$ 을 "nice" 라고 부릅니다. $2010, 2011, 2012, \ldots, 2019$ 의 열 개 정수 중 nice 한 수가 몇 개인지 셉니다.

주어진 것: $m$ 은 $1$ 과 $m$ 을 포함해 정확히 네 개의 양의 약수를 가진 양의 정수.; $n$ 은 그 네 약수의 합.; 후보 값: $n \in \{2010, 2011, 2012, \ldots, 2019\}$ (연속한 열 개 정수).; 선택지: (A) $1$, (B) $2$, (C) $3$, (D) $4$, (E) $5$.

구하는 것: $2010$ 부터 $2019$ 까지의 열 개 정수 중 nice 한 수의 개수.

이해

계획

주요 도구: #4 변수 도입하기

보조 도구: #7 작은 문제로 쪼개기, #3 가능성 지우기, #2 빠짐없이 나열하기

"nice" 라는 말은 약수 합 조건을 숨기고 있으므로, 첫 수는 소수에 이름을 붙이는 것입니다. 도구 #4(변수 도입하기): $m = pq$ 로 두고 그 약수 합 $1 + p + q + pq$ 를 곱의 형태 $(1+p)(1+q)$ 로 바꾸면, 흐릿한 질문 "$n$ 이 nice 한가?" 가 날카로운 판정 "$n$ 을 각각 소수보다 $1$ 큰 두 인수로 쪼갤 수 있는가?" 로 바뀝니다. 도구 #7(작은 문제로 쪼개기) 은 네 약수 수를 $p^{3}$ 과 $pq$ 두 모양으로 먼저 나눕니다. 도구 #3(가능성 지우기) 는 홀짝성으로 다섯 개의 홀수를 한 번에 제거합니다. 도구 #2(빠짐없이 나열하기) 는 남은 짝수들을 각각의 인수쌍으로 검사합니다.

실행 — 정답: A

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

네 약수 수의 두 가지 모양

양의 정수가 약수를 정확히 네 개 가지는 경우는 딱 두 가지입니다.
소수 $p$ 에 대해 $p^{3}$ 이면 약수는 $1, p, p^{2}, p^{3}$.
서로 다른 두 소수 $p, q$ 에 대해 $pq$ 이면 약수는 $1, p, q, pq$.
다른 어떤 인수분해 모양도 약수를 정확히 네 개 만들지 못합니다.

$$m = p^{3} \Rightarrow \{1, p, p^{2}, p^{3}\} \quad\text{또는}\quad m = pq \Rightarrow \{1, p, q, pq\}$$

💡 약수 개수는 (각 지수 $+1$) 들의 곱과 같고, $4$ 는 $4$ 자체나 $2 \times 2$ 로만 나오므로 $p^{3}$ 또는 $pq$.

#4 변수 도입하기 6.EE.A.3 단계 2

약수 합을 인수분해하기

$m = pq$ 모양을 봅니다.
네 약수의 합은 $1 + p + q + pq$.
앞의 두 항과 뒤의 두 항에서 각각 $(1+p)$ 를 묶어냅니다: $1 + p + q + pq = (1+p) + q(1+p) = (1+p)(1+q)$.
따라서 이 모양에서 $n$ 이 nice 한 것은 서로 다른 소수 $p, q$ 에 대해 $n = (1+p)(1+q)$ 일 때 — 즉 $n$ 을 곱 $a \cdot b$ 로 쓰되 $a - 1$ 과 $b - 1$ 이 모두 소수일 때입니다.

$$1 + p + q + pq = (1+p)(1+q)$$

💡 네 항의 합을 하나의 곱으로 묶는 것이 핵심 — "$n$ 이 nice 한가?" 가 인수분해 문제로 바뀐다.

#2 빠짐없이 나열하기 6.EE.A.2 단계 3

세제곱 모양은 넘어가 버린다

$m = p^{3}$ 모양을 확인합니다.
약수 합은 $1 + p + p^{2} + p^{3}$.
소수 $p = 2, 3, 5, 7, 11, 13$ 에 대해 각각 $15, 40, 156, 400, 1464, 2380$.
값이 $1464$ 에서 $2380$ 으로 곧장 뛰어 $2010$–$2019$ 구간 전체를 건너뜁니다.
그래서 세제곱 모양은 nice 한 수를 만들 수 없고, $pq$ 모양만 문제가 됩니다.

$$1 + 11 + 11^{2} + 11^{3} = 1464, \qquad 1 + 13 + 13^{2} + 13^{3} = 2380$$

💡 세제곱은 너무 빨리 커져서 이웃한 약수 합이 열 개짜리 목표 구간을 훌쩍 뛰어넘는다.

#3 가능성 지우기 2.OA.C.3 단계 4

홀수는 nice 할 수 없다

$p, q$ 중 짝수 소수 $2$ 는 많아야 하나뿐이므로 적어도 하나는 홀수 소수입니다.
그러면 인수 $1 + p$ 또는 $1 + q$ 중 적어도 하나가 짝수라 곱 $n = (1+p)(1+q)$ 는 짝수가 됩니다.
따라서 모든 nice 한 수는 짝수이고, 홀수 다섯 개 $2011, 2013, 2015, 2017, 2019$ 는 즉시 제거됩니다.

$$n = (1+p)(1+q) \text{ 는 짝수} \;\Rightarrow\; n \in \{2010, 2012, 2014, 2016, 2018\}$$

💡 홀수 소수에 $1$ 을 더하면 짝수이고, 짝수 인수를 품은 곱은 모두 짝수다.

#2 빠짐없이 나열하기 4.OA.B.4 단계 5

다섯 짝수 후보 검사

각 짝수 후보에 대해 $a, b \ge 3$ 인 인수쌍 $a \cdot b$ 를 나열하고 $a - 1$ 과 $b - 1$ 이 모두 소수인지 확인합니다.
$2010$: 쌍 $6 \cdot 335$ 와 $30 \cdot 67$ 은 짝 $334$ 와 $66$ 을 줘 결코 둘 다 소수가 아닙니다.
$2012 = 4 \cdot 503$: $503 - 1 = 502 = 2 \cdot 251$ 은 소수가 아닙니다.
$2014 = 38 \cdot 53$: $37$ 은 소수지만 $52$ 는 아닙니다.
$2018 = 2 \cdot 1009$ 는 두 부분이 모두 $\ge 3$ 인 인수쌍이 없습니다.
네 개 모두 실패.

$$2010,\; 2012,\; 2014,\; 2018:\ a-1,\, b-1 \text{ 이 모두 소수인 } a \cdot b \text{ 분해 없음}$$

💡 각 인수쌍을 "소수보다 $1$ 큰지" 판정에 통과시키면 모든 경우가 금세 소진된다.

#3 가능성 지우기 4.OA.B.4 단계 6

$2016$ 이 유일한 nice 한 수

이제 $2016$.
$4 \cdot 504$ 로 쪼개면 $a - 1 = 3$ 과 $b - 1 = 503$ 이 모두 소수이고 서로 다릅니다.
그래서 $m = 3 \cdot 503 = 1509$ 가 됩니다 — 그 약수 $1, 3, 503, 1509$ 의 합이 정확히 $2016$.
$2016$ 은 nice 하고 나머지 아홉 수는 아니므로, 집합에서 nice 한 수는 정확히 하나, 개수는 $1$, 선택지 $\textbf{(A)}$.

$$2016 = 4 \cdot 504 = (1+3)(1+503), \qquad 1 + 3 + 503 + 1509 = 2016$$

💡 유효한 분해 하나 — $3$ 과 $503$ 이 모두 소수 — 면 $2016$ 을 nice 하게 만들기에 충분하고, 구간에서 그런 분해를 갖는 수는 이것뿐이다.

[1] #7 4.OA.B.4 양의 정수가 약수를 정확히 네 개 가지는 경우는 딱 두 가지입니다. 소수 $p$ 에 대해 $p^{3}$ 이면 약수는 $1, p, p^{2}, p

[2] #4 6.EE.A.3 $m = pq$ 모양을 봅니다. 네 약수의 합은 $1 + p + q + pq$. 앞의 두 항과 뒤의 두 항에서 각각 $(1+p)$ 를 묶어냅니다

[3] #2 6.EE.A.2 $m = p^{3}$ 모양을 확인합니다. 약수 합은 $1 + p + p^{2} + p^{3}$. 소수 $p = 2, 3, 5, 7, 11, 13

[4] #3 2.OA.C.3 $p, q$ 중 짝수 소수 $2$ 는 많아야 하나뿐이므로 적어도 하나는 홀수 소수입니다. 그러면 인수 $1 + p$ 또는 $1 + q$ 중 적어

[5] #2 4.OA.B.4 각 짝수 후보에 대해 $a, b \ge 3$ 인 인수쌍 $a \cdot b$ 를 나열하고 $a - 1$ 과 $b - 1$ 이 모두 소수인지 확인

[6] #3 4.OA.B.4 이제 $2016$. $4 \cdot 504$ 로 쪼개면 $a - 1 = 3$ 과 $b - 1 = 503$ 이 모두 소수이고 서로 다릅니다. 그래

검토

합리성 확인: 개수 $1$ 은 선택지 (A) 와 일치합니다. $2016$ 재확인: $m = 1509 = 3 \times 503$ 의 약수 $1, 3, 503, 1509$ 의 합이 $2016$ 이고, $503$ 은 소수($22$ 이하의 어떤 소수로도 나눠지지 않음)입니다. 홀짝성 필터는 빈틈이 없어 — 모든 nice 한 수는 짝수여야 함 — 다섯 짝수 중 $2016$ 만 살아남았는데, 이는 (작은 짝수) $\times$ (큰 소수보다 $1$ 큰 수) 로 분해되며 두 부분이 모두 소수보다 $1$ 큰 유일한 수이기 때문입니다.

대안 접근: 도구 #2(빠짐없이 나열하기) 를 끝까지: 각 작은 소수 $p$ 에 대해 $(1+p)(1+q)$ 가 $[2010, 2019]$ 에 들어가게 하는 $q$ 를 묻습니다. $p = 2 \to 3(1+q)$ 는 $q = 669$ 또는 $671$ 을 강제하는데 둘 다 합성수. $p = 3 \to 4 \cdot 504$ 는 $q = 503$ (소수) 를 줘 $2016$ 에 적중. 더 큰 작은 소수들도 $2016$ 에 도달합니다 ($p = 7 \to 8 \cdot 252$, $q = 251$; $p = 11 \to 12 \cdot 168$, $q = 167$) 그리고 구간의 다른 곳엔 도달하지 않습니다. $[2010, 2019]$ 의 다른 어떤 정수도 결코 만들어지지 않으므로 개수는 $1$.

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

2.OA.C.3 물건 묶음이 홀수인지 짝수인지 판정하기 (모든 nice 한 수가 짝수임을 홀짝성으로 논증해 다섯 홀수 후보를 제거.)
4.OA.B.4 인수쌍을 모두 찾고 배수를 인식하며 소수·합성수 판별하기 (네 약수 수를 $p^{3}$ 또는 $pq$ 로 분류하고, 각 짝수 후보의 인수쌍을 소수보다 $1$ 큰 조건으로 검사.)
6.EE.A.2 문자가 수를 나타내는 식을 쓰고 읽고 값 구하기 (세제곱 모양의 약수 합 $1 + p + p^{2} + p^{3}$ 을 작은 소수에 대해 계산해 목표 구간을 건너뜀을 보임.)
6.EE.A.3 연산의 성질을 적용해 동치인 식 만들기 (약수 합 $1 + p + q + pq$ 를 $(1+p)(1+q)$ 로 인수분해 — niceness 를 인수분해 판정으로 바꾸는 핵심.)

⭐ 약수가 정확히 네 개인 수는 $pq$ 이고 그 약수 합은 $(1+p)(1+q)$ 로 인수분해되니, "nice" 는 결국 $n$ 을 각각 소수보다 $1$ 큰 두 부분으로 쪼갤 수 있다는 뜻 — $2016 = 4 \cdot 504 = (1+3)(1+503)$ 만 되므로 답은 $1$, 선택지 (A).