AMC 10 · 2020 · #25

학년 7 arithmetic

유형 Branching State Enumeration └ 세부 유형 Numeric Operation Tree

prime-factorizationrecursive-sequencecombinations-basicdivisor-count easier-related-problemcaseworkidentify-subproblems ↑ 선수 지식: prime-factorizationcombinations-basic

📏 긴 풀이 💡 3 개 인사이트

문제

Let $D(n)$ denote the number of ways of writing the positive integer $n$ as a product $n = f_1\cdot f_2\cdots f_k,$ where $k\ge1$ , the $f_i$ are integers strictly greater than $1$ , and the order in which the factors are listed matters (that is, two representations that differ only in the order of the factors are counted as distinct). For example, the number $6$ can be written as $6$ , $2\cdot 3$ , and $3\cdot2$ , so $D(6) = 3$ . What is $D(96)$ ?

답을 골라 클릭하세요.

(A)

112

(B)

128

(C)

144

(D)

172

(E)

184

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $96$ 을 $1$ 보다 큰 정수들의 순서 있는 곱으로 나타내는 방법의 수. (순서 다른 것을 다르게 셈 — $2 \cdot 3 \ne 3 \cdot 2$.) $D(96)$ 의 값?

주어진 것: $96 = 2^5 \cdot 3$; 각 인수 $f_i > 1$; 순서가 다르면 다른 곱으로 셈; 한 개짜리 인수분해 ($k = 1$) 인 $96$ 자체도 한 번 셈; 예: $D(6) = 3$ — $6, \;\; 2 \cdot 3, \;\; 3 \cdot 2$; 선택지: (A) $112$, (B) $128$, (C) $144$, (D) $172$, (E) $184$

구하는 것: $D(96)$ — 순서 있는 인수분해 총수

이해

문제 재정리: $96$ 을 $1$ 보다 큰 정수들의 순서 있는 곱으로 나타내는 방법의 수. (순서 다른 것을 다르게 셈 — $2 \cdot 3 \ne 3 \cdot 2$.) $D(96)$ 의 값?

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #2 빠짐없이 나열하기, #7 작은 문제로 쪼개기, #5 패턴 찾기, #13 대수로 바꾸기, #6 추측하고 확인하기

도구 #9(더 쉬운 문제): 문제에 주어진 $D(6) = 3$ 을 검증용 작은 사례로. 도구 #2(나열): 인수 개수 $k = 1, \ldots, 6$ 으로 분류 ($2^k \le 96$ 필요라 $k \le 6$). 도구 #7(쪼개기): 각 $k$ 에 대해 (a) 단일 $3$ 의 위치 (b) $5$ 개의 $2$ 분배 — 두 부분으로 분리. 도구 #5(패턴): 각 $k$ 별 개수가 $k \cdot \binom{5}{k-1}$. 도구 #13(대수): 닫힌 공식으로 합산. 도구 #6(추측·확인): 작은 사례 $D(6) = 3$ 으로 공식 확인.

실행 — 정답: A

#9 더 쉬운 문제로 줄이기 6.NS.B.4 단계 1

$96 = 2^5 \cdot 3$ 으로 소인수분해.
임의의 순서 인수분해 $96 = f_1 \cdots f_k$ ($f_i \ge 2$) 는 $f_i = 2^{a_i} 3^{b_i}$ 형태, $a_i, b_i \ge 0$ 이고 $a_i + b_i \ge 1$ (조건: $f_i > 1$), $\sum a_i = 5$, $\sum b_i = 1$.

$$f_i = 2^{a_i} 3^{b_i}, \;\; a_i + b_i \ge 1, \;\; \sum a_i = 5, \;\; \sum b_i = 1$$

💡 $2$ 의 지수와 $3$ 의 지수를 분리해 추적.

#7 작은 문제로 쪼개기 7.SP.C.8 단계 2

$\sum b_i = 1$ 이라 정확히 한 인수 (위치 $i \in \{1, \ldots, k\}$) 가 $b_i = 1$ 이고 나머지는 $b_j = 0$.
$3$ 이 놓일 슬롯 선택 $k$ 가지.

$$3 \text{ 의 위치: } k \text{ 가지}$$

💡 단일 $3$ 의 슬롯이 $k$ 개 중 하나.

#13 대수로 바꾸기 7.SP.C.8 단계 3

$b_j = 0$ 인 나머지 $k - 1$ 슬롯은 $a_j \ge 1$ 필요 (안 그러면 $f_j = 1$).
$3$ 슬롯은 $a_i \ge 0$ 허용.
총 $2$ 개수 $5$ 분배: $a_j = 1 + c_j$ ($c_j \ge 0$) 치환하면 $a_i + \sum (1 + c_j) = 5$, 즉 $a_i + \sum c_j = 6 - k$.
$k$ 개의 비음 정수 합 $6 - k$ — 스타스 앤 바스 (별과 막대): $\binom{(6-k) + (k-1)}{k-1} = \binom{5}{k-1}$.

$$2 \text{ 분배: } \binom{5}{k - 1}$$

💡 $3$ 가 없는 슬롯엔 $2$ 한 개씩 미리 채우고 나머지 자유 분배.

#2 빠짐없이 나열하기 7.SP.C.8 단계 4

곱: 인수 $k$ 개인 순서 인수분해 수 $$N_k \;=\; k \cdot \binom{5}{k - 1}.$$ 범위: $2^k \le 96 \Rightarrow k \le 6$.
각각 계산: • $k = 1$: $N_1 = 1 \cdot \binom{5}{0} = 1$ • $k = 2$: $N_2 = 2 \cdot \binom{5}{1} = 10$ • $k = 3$: $N_3 = 3 \cdot \binom{5}{2} = 30$ • $k = 4$: $N_4 = 4 \cdot \binom{5}{3} = 40$ • $k = 5$: $N_5 = 5 \cdot \binom{5}{4} = 25$ • $k = 6$: $N_6 = 6 \cdot \binom{5}{5} = 6$

$$N_k = k \binom{5}{k-1}: \;\; 1, 10, 30, 40, 25, 6$$

💡 6 개 작은 사례 — 파스칼 한 줄 × $k$.

#7 작은 문제로 쪼개기 5.OA.A.1 단계 5

합: $D(96) = 1 + 10 + 30 + 40 + 25 + 6 = 112$.
선택지 $(A)$.

$$D(96) = 1 + 10 + 30 + 40 + 25 + 6 = 112 \Rightarrow \textbf{(A)}$$

💡 6 항 덧셈 — $112$.

#6 추측하고 확인하기 3.OA.B.5 단계 6

작은 사례 점검: $D(6) = ?$ — $6 = 2^1 \cdot 3^1$ 이라 $\sum a_i = 1, \sum b_i = 1$.
각 $k$: • $k = 1$: $1 \cdot 1 = 1$ ("$6$") • $k = 2$: $2 \cdot 1 = 2$ ("$2 \cdot 3$", "$3 \cdot 2$") 합 $= 1 + 2 = 3 = D(6)$ ✓ — 문제 진술과 일치.

$$D(6) = 1 + 2 = 3 \;\; \checkmark$$

💡 같은 공식이 $D(6) = 3$ 을 그대로 복원.

[1] #9 6.NS.B.4 $96 = 2^5 \cdot 3$ 으로 소인수분해. 임의의 순서 인수분해 $96 = f_1 \cdots f_k$ ($f_i \ge 2$) 는 $

[2] #7 7.SP.C.8 $\sum b_i = 1$ 이라 정확히 한 인수 (위치 $i \in \{1, \ldots, k\}$) 가 $b_i = 1$ 이고 나머지는 $b_

[3] #13 7.SP.C.8 $b_j = 0$ 인 나머지 $k - 1$ 슬롯은 $a_j \ge 1$ 필요 (안 그러면 $f_j = 1$). $3$ 슬롯은 $a_i \ge 0

[4] #2 7.SP.C.8 곱: 인수 $k$ 개인 순서 인수분해 수 $$N_k \;=\; k \cdot \binom{5}{k - 1}.$$ 범위: $2^k \le 96 \

[5] #7 5.OA.A.1 합: $D(96) = 1 + 10 + 30 + 40 + 25 + 6 = 112$. 선택지 $(A)$.

[6] #6 3.OA.B.5 작은 사례 점검: $D(6) = ?$ — $6 = 2^1 \cdot 3^1$ 이라 $\sum a_i = 1, \sum b_i = 1$. 각 $k

검토

합리성 확인: 두 단계 점검. (1) $D(6) = 3$ 확인 — 공식 $N_k = k \binom{5}{k-1}$ 일반화가 정확. (2) 총 $112$ 가 선택지 $100$ 과 $144$ 사이의 적절한 값. $N_k$ 분포가 $k = 4$ 에서 $40$ 으로 정점 — $96$ 의 인수 평균 길이가 $\sim \log_2 96 \approx 6.6$ (최소 인수 $2$) 와 일관. $(A)$ 확정.

대안 접근: 도구 #2(나열) 직접 — 참조 풀이 1 식. 각 $k$ 에 대해 중복집합 $(2^a, 2^b, \ldots)$ 분할을 손으로 열거하고 $3$ 위치 곱. 더 번거롭지만 $112$ 같음. 또는 도구 #11(거꾸로): 재귀 $D(n) = 1 + \sum_{d | n, 1 < d < n} D(n/d)$ 로 $D(2), D(4), D(6), D(8), D(12), \ldots, D(96)$ 차례로 계산.

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

3.OA.B.5 연산의 성질을 곱셈·나눗셈 전략으로 활용 (작은 사례 $D(6) = 3$ 의 직접 열거 검증.)
5.OA.A.1 괄호·중괄호 사용 수식 평가 ($1 + 10 + 30 + 40 + 25 + 6 = 112$ 합산.)
6.NS.B.4 두 수의 최대공약수·최소공배수 ($96 = 2^5 \cdot 3$ 소인수분해 및 소수 지수 분리 추적.)
7.SP.C.8 조직된 목록·표로 복합사건 수 세기 (스타스 앤 바스 — $5$ 개의 $2$ 를 $k$ 슬롯에 $k - 1$ 최소 $1$ 조건으로 분배 $\binom{5}{k-1}$.)

⭐ 이 AMC 10 문제는 7학년 경우의 수만 알면 풀려요 — $96 = 2^5 \cdot 3$ 이라 각 인수 개수 $k$ 마다 $3$ 의 위치 ($k$ 가지) × $5$ 개의 $2$ 분배 ($\binom{5}{k-1}$, 스타스 앤 바스): $k = 1$ 부터 $6$ 까지 합하면 $1 + 10 + 30 + 40 + 25 + 6 = 112$.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: A

검토

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

비슷한 유형 더 풀어보기