AMC 10 · 2020 · #25
Grade 7 arithmeticProblem
Let D(n) denote the number of ways of writing the positive integer n as a productn=f1⋅f2⋯fk,where k≥1, the fi 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⋅3, and 3⋅2, so D(6)=3. What is D(96)?
Pick an answer.
AMC 10 2020 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
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)$.
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$
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
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$.
💡 Track the $2$'s and the single $3$ separately.
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$.
💡 The single $3$ has $k$ slots to live in.
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}$.
💡 Force each non-$3$ slot to take a $2$ first, then distribute leftover $2$'s freely.
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$
💡 Six small cases, each is one row of Pascal scaled by $k$.
5.OA.A.1 Step 5 - Sum: $D(96) = 1 + 10 + 30 + 40 + 25 + 6 = 112$.
- Matches choice $(A)$.
💡 Straight addition of six counts gives $112$.
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.
💡 The same formula on the toy case $96 \to 6$ recovers the given $D(6) = 3$.
6.NS.B.4 Factor $96 = 2^5 \cdot 3$. Any factorization $96 = f_1 \cdot f_2 \cdots f_k$ (or 7.SP.C.8 Since $\sum b_i = 1$, exactly one factor (say at position $i$, with $i \in {1, 7.SP.C.8 The remaining $k - 1$ factors have $b_j = 0$, so they require $a_j \ge 1$ (other 7.SP.C.8 Multiplying: the number of ordered factorizations with exactly $k$ factors is
$$ 5.OA.A.1 Sum: $D(96) = 1 + 10 + 30 + 40 + 25 + 6 = 112$. Matches choice $(A)$. 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.5Apply 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.1Use 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.4Find 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.8Find 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$.
⭐ 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$.
More like this
Same archetype — closest grade level first.