AMC 10 · 2020 · #25

Grade 7 arithmetic

prime-factorizationrecursive-sequencecombinations-basicdivisor-count easier-related-problemcaseworkidentify-subproblems ↑ Prerequisites: prime-factorizationcombinations-basic

📏 Long solution 💡 3 insights

Problem

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)$ ?

$\textbf{(A) } 112 \qquad\textbf{(B) } 128 \qquad\textbf{(C) } 144 \qquad\textbf{(D) } 172 \qquad\textbf{(E) } 184$

Pick an answer.

(A)

112

(B)

128

(C)

144

(D)

172

(E)

184

View mode:

Toolkit + CCSS Solution

Understand

Restated: Count the ordered factorizations of $96$ into factors each $> 1$. (Order matters — $2 \cdot 3 \ne 3 \cdot 2$.) Find $D(96)$.

Givens: $96 = 2^5 \cdot 3$; Each factor $f_i > 1$; Two factorizations differing only in order are counted as distinct; Single-factor case ($k = 1$) counts $96$ itself once; Example: $D(6) = 3$ — namely $6, \;\; 2 \cdot 3, \;\; 3 \cdot 2$; Answer choices: (A) $112$, (B) $128$, (C) $144$, (D) $172$, (E) $184$

Unknowns: $D(96)$ — total ordered factorizations

Understand

Restated: Count the ordered factorizations of $96$ into factors each $> 1$. (Order matters — $2 \cdot 3 \ne 3 \cdot 2$.) Find $D(96)$.

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #2 Make a Systematic List, #7 Identify Subproblems, #5 Look for a Pattern, #13 Convert to Algebra, #6 Guess and Check

Tool #9 (Easier Problem): the verifier $D(6) = 3$ is given — anchor on this small case. Tool #2 (Systematic List): casework on $k$ = number of factors ($k = 1, 2, 3, 4, 5, 6$) — at most $6$ factors since the smallest factor is $2$ and $2^6 = 64 < 96 < 128 = 2^7$. Tool #7 (Subproblems): for each $k$, separately count (a) where to place the single $3$ and (b) how to distribute the remaining powers of $2$ among the factors. Tool #5 (Pattern): the per-$k$ count factors into $k \cdot \binom{5}{k-1}$ via stars-and-bars. Tool #13 (Algebra): sum the closed form using $\sum k \binom{n}{k-1} = (n+2) 2^{n-1}$ — actually here a clean direct sum. Tool #6 (Guess and Check) cross-verifies via $D(6) = 3$.

Execute — Answer: A

#9 Solve an Easier Related Problem 6.NS.B.4 Step 1

Factor $96 = 2^5 \cdot 3$.
Any factorization $96 = f_1 \cdot f_2 \cdots f_k$ (ordered, $f_i \ge 2$) corresponds to choosing nonnegative integers $a_i, b_i \ge 0$ with each $a_i + b_i \ge 1$ (so $f_i = 2^{a_i} 3^{b_i} > 1$), such that $\sum a_i = 5$ and $\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$$

💡 Track the $2$'s and the single $3$ separately.

#7 Identify Subproblems 7.SP.C.8 Step 2

Since $\sum b_i = 1$, exactly one factor (say at position $i$, with $i \in \{1, \ldots, k\}$) carries $b_i = 1$ and all others have $b_j = 0$.
There are $k$ choices for which slot gets the $3$.

$$\text{Place the } 3: k \text{ choices}$$

💡 The single $3$ has $k$ slots to live in.

#13 Convert to Algebra 7.SP.C.8 Step 3

The remaining $k - 1$ factors have $b_j = 0$, so they require $a_j \ge 1$ (otherwise $f_j = 1$).
The chosen slot has $b_i = 1$, so it allows $a_i \ge 0$.
Distribute $5$ total $2$'s subject to: $a_i \ge 0$ and $a_j \ge 1$ for the other $k - 1$ slots.
Substitute $a_j = 1 + c_j$ with $c_j \ge 0$, giving $a_i + \sum (1 + c_j) = 5$, i.e., $a_i + \sum c_j = 6 - k$.
This is $k$ nonneg integers summing to $6 - k$ — stars and bars: $\binom{(6-k) + (k-1)}{k-1} = \binom{5}{k-1}$.

$$\text{Distribute the } 2\text{'s}: \binom{5}{k - 1}$$

💡 Force each non-$3$ slot to take a $2$ first, then distribute leftover $2$'s freely.

#2 Make a Systematic List 7.SP.C.8 Step 4

Multiplying: the number of ordered factorizations with exactly $k$ factors is $$N_k \;=\; k \cdot \binom{5}{k - 1}.$$ Valid range: $k$ goes from $1$ (the trivial $96$ alone) up to $6$ (since the minimum product with $k$ factors each $\ge 2$ is $2^k$, requiring $2^k \le 96$, i.e., $k \le 6$).
Compute each: • $k = 1$: $N_1 = 1 \cdot \binom{5}{0} = 1 \cdot 1 = 1$ • $k = 2$: $N_2 = 2 \cdot \binom{5}{1} = 2 \cdot 5 = 10$ • $k = 3$: $N_3 = 3 \cdot \binom{5}{2} = 3 \cdot 10 = 30$ • $k = 4$: $N_4 = 4 \cdot \binom{5}{3} = 4 \cdot 10 = 40$ • $k = 5$: $N_5 = 5 \cdot \binom{5}{4} = 5 \cdot 5 = 25$ • $k = 6$: $N_6 = 6 \cdot \binom{5}{5} = 6 \cdot 1 = 6$

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

💡 Six small cases, each is one row of Pascal scaled by $k$.

#7 Identify Subproblems 5.OA.A.1 Step 5

Sum: $D(96) = 1 + 10 + 30 + 40 + 25 + 6 = 112$.
Matches choice $(A)$.

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

💡 Straight addition of six counts gives $112$.

#6 Guess and Check 3.OA.B.5 Step 6

Sanity check via the simple example.
$D(6) = ?$ — here $6 = 2^1 \cdot 3^1$, so $\sum a_i = 1, \sum b_i = 1$.
For each $k$: place the $3$ ($k$ ways) and distribute one $2$ subject to the constraints.
• $k = 1$: $1 \cdot 1 = 1$ (just "$6$") • $k = 2$: $2 \cdot 1 = 2$ ("$2 \cdot 3$" and "$3 \cdot 2$") Sum $= 1 + 2 = 3 = D(6)$ ✓ — matches the problem statement.

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

💡 The same formula on the toy case $96 \to 6$ recovers the given $D(6) = 3$.

[1] #9 6.NS.B.4 Factor $96 = 2^5 \cdot 3$. Any factorization $96 = f_1 \cdot f_2 \cdots f_k$ (or

[2] #7 7.SP.C.8 Since $\sum b_i = 1$, exactly one factor (say at position $i$, with $i \in {1,

[3] #13 7.SP.C.8 The remaining $k - 1$ factors have $b_j = 0$, so they require $a_j \ge 1$ (other

[4] #2 7.SP.C.8 Multiplying: the number of ordered factorizations with exactly $k$ factors is $$

[5] #7 5.OA.A.1 Sum: $D(96) = 1 + 10 + 30 + 40 + 25 + 6 = 112$. Matches choice $(A)$.

[6] #6 3.OA.B.5 Sanity check via the simple example. $D(6) = ?$ — here $6 = 2^1 \cdot 3^1$, so $

Review

Reasonableness: Two layers of sanity. (1) The $D(6) = 3$ check matches the problem's worked example, confirming the formula $N_k = k \binom{5}{k-1}$ generalizes correctly. (2) The total $112$ is sandwiched between the choices $100$ (too low, would miss the $k = 4$ bulk) and $144$ (too high). Distribution of $N_k$ peaks at $k = 4$ with $40$, consistent with $96$ having $5$ twos and $1$ three (typical factorization length $\sim \log_2 96 \approx 6.6$ at minimum factor size $2$). Choice $(A)$ confirmed.

Alternative: Tool #2 (Systematic List) by casework on number of factors — the reference's first solution. It directly enumerates the multiset partitions $(2^a, 2^b, \ldots)$ for each $k$, separately counts where the $3$ multiplies, and sums. More tedious but verifies the same $112$. Or Tool #11 (Work Backwards): define recursively $D(n) = 1 + \sum_{d | n, 1 < d < n} D(n/d)$ and compute $D(2), D(4), D(6), D(8), D(12), \ldots, D(96)$. Slow but transparent.

CCSS standards used (min grade 7)

3.OA.B.5 Apply properties of operations as strategies to multiply and divide (Verifying the formula on the small case $D(6) = 3$ by direct enumeration.)
5.OA.A.1 Use parentheses, brackets, or braces in numerical expressions and evaluate (Adding $1 + 10 + 30 + 40 + 25 + 6$ to get the total $D(96) = 112$.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Factoring $96 = 2^5 \cdot 3$ and tracking the prime exponents separately across all factors.)
7.SP.C.8 Find probabilities of compound events using organized lists, tables, and simulation (Counting by stars and bars: for each $k$, distribute $5$ twos into $k$ slots subject to $k - 1$ minimum-$1$ constraints — $\binom{5}{k - 1}$ ways.)

⭐ This AMC 10 problem only needs Grade 7 counting: $96 = 2^5 \cdot 3$, so for each number of factors $k$ pick where the $3$ lives ($k$ ways) and distribute the $5$ twos among the $k$ slots ($\binom{5}{k-1}$ ways via stars and bars) — sum $k \binom{5}{k-1}$ from $k = 1$ to $6$: $1 + 10 + 30 + 40 + 25 + 6 = 112$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: A

Review

CCSS standards used (min grade 7)

More like this