AMC 10 · 2020 · #25

Grade 7 arithmetic

Archetype Branching State Enumeration └ Sub-archetype Numeric Operation Tree

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

📏 Long solution 💡 3 insights

Problem

Count the ordered factorizations of 96 into factors each ＞ 1. (Order matters — 2 · 3 ≠ 3 · 2.) Find D(96).

Pick an answer.

(A)

112

(B)

128

(C)

144

(D)

172

(E)

184

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

How to solve

Strategy Solve an Easier Related Problem

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⁶ = 64 ＜ 96 ＜ 128 = 2⁷. 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 · C(5, k-1) via stars-and-bars. Tool #13 (Algebra): sum the closed form using Σ k C(n, k-1) = (n+2) 2ⁿ⁻¹ — actually here a clean direct sum. Tool #6 (Guess and Check) cross-verifies via D(6) = 3.

1STEP 1

Write 96 = 2⁵ · 3, so an ordered list f₁…f_k needs a_i + b_i ≥ 1 with Σ a_i = 5 and Σ b_i = 1.

f_i = 2^a_i 3^b_i, a_i + b_i ≥ 1, Σ a_i = 5, Σ b_i = 1

2STEP 2

Since Σ b_i = 1, exactly one slot carries the 3 and the rest carry none — that gives k choices for where the 3 lives.

Place the 3: k choices

3STEP 3

Each non-3 slot needs a 2 first (else it equals 1); distributing the leftover 2's by stars and bars gives C(5, k - 1) ways.

Distribute the 2's: C(5, k - 1)

4STEP 4

So N_k = k · C(5, k - 1), and since 2^k ≤ 96 means k ≤ 6, over k = 1…6 this gives 1, 10, 30, 40, 25, 6.

N_k = k C(5, k-1): 1, 10, 30, 40, 25, 6

5STEP 5

Adding them: 1 + 10 + 30 + 40 + 25 + 6 = 112, which is choice (A).

D(96) = 1 + 10 + 30 + 40 + 25 + 6 = 112 → (A)

6STEP 6

Sanity check: for 6 = 2¹ · 3¹ the same rule gives 1 + 2 = 3, matching the given D(6) = 3.

D(6) = 1 + 2 = 3 ✓

Answer

112

Two layers of sanity. (1) The D(6) = 3 check matches the problem's worked example, confirming the formula N_k = k C(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 ∼ log₂ 96 ≈ 6.6 at minimum factor size 2). Choice (A) confirmed.

💡Key takeaway

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

More like this