Printable

2020 AMC 10B Problem 25

2020 AMC 10B Problem 25AMC 10 Step by Step

Name: Date: September 13, 2026

Distributions & Stars and Bars · difficulty 5 of 5 · about 10 min · position P21-25

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$

Answer

Key insight

96 = 2^5 * 3; with k factors, place the 3 in one slot, then give every other slot a 2 and distribute the rest: k * C(5, k-1).

Solution

Factor $96 = 2^5 \cdot 3$ . An ordered factorization into $k$ factors is the same as deciding, for each prime, how its copies are split among the $k$ ordered slots, subject to every slot receiving something (so that no factor equals $1$ ). Since there are only six prime factors, $1 \le k \le 6$ .

Fix $k$ . The single $3$ goes into one of the $k$ slots ( $k$ choices). That slot is already bigger than $1$ ; the other $k - 1$ slots each need at least one $2$ . Give each of them one $2$ , leaving $5 - (k-1) = 6 - k$ twos to distribute freely among all $k$ slots: by stars and bars, $\binom{(6-k) + (k-1)}{k-1} = \binom{5}{k-1}$ ways.

So the number of ordered factorizations with $k$ factors is $k \binom{5}{k-1}$ :

$k$	1	2	3	4	5	6
$k\binom{5}{k-1}$	$1$	$10$	$30$	$40$	$25$	$6$

Sum: $1 + 10 + 30 + 40 + 25 + 6 = 112$ .

The answer is $\boxed{\textbf{(A)}\ 112}$ .

Why this works

Ordered factorizations are distributions of prime factors into labeled boxes with the constraint "no empty box." When one prime appears once, it acts as a wildcard that fills one box for free, and the remaining prime copies are distributed with the standard "at least one each" stars-and-bars trick (pre-place one in each needy box). Casework on the number of factors keeps the constraint manageable.

Alternative approach

Recursion: $D(n) = 1 + \sum_{d \mid n,\ 1 < d < n} D(n/d)$ (pick the first factor $d$ ). Build up $D(2^j) = 2^{j-1}$ and $D(3\cdot 2^j)$ for $j = 0, 1, \dots, 5$ : $D(3) = 1$ , $D(6) = 3$ , $D(12) = 8$ , $D(24) = 20$ , $D(48) = 48$ , $D(96) = 112$ . This is slower but excellent as a check.

The trap

Distributing the five 2's without requiring every factor to exceed 1, which counts factors equal to 1 and overcounts badly.

Common mistakes

Distributing the five 2's without requiring every factor to exceed 1, which counts factors equal to 1 and overcounts badly.
Forgetting the factor $k$ for the position of the $3$ , which gives $\sum \binom{5}{k-1} = 32$ , or treating factorizations as unordered.

Techniques

Map the objects to something easier to count · Split into exhaustive cases and handle each