2020 AMC 10B Problem 25

P21-25~10 minPrint

Distributions & Stars and Bars Basic Counting Divisibility & Factors Map the objects to something easier to count Split into exhaustive cases and handle each

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

Show solution without answering

Key insight

96 is five 2s times a 3. Put the 3 in one factor, give every other factor one 2, then share out the leftover 2s freely among all the factors.

Solution

Factor. $96 = 2 \times 2 \times 2 \times 2 \times 2 \times 3 = 2^5 \times 3$ . Writing $96$ as an ordered product means sharing these six prime factors among the factors $f_1, f_2, \ldots, f_k$ in order, so that each factor gets at least one prime (no factor may be $1$ ). With only six primes, $k$ is between $1$ and $6$ .
A small case first: $k = 2$ . The $3$ goes to $f_1$ or $f_2$ : $2$ choices. The other factor still needs at least one $2$ , so give it one. The remaining four $2$ s can be split between $f_1$ and $f_2$ as $4+0, 3+1, 2+2, 1+3, 0+4$ : $5$ ways. Total $2 \times 5 = 10$ . Check: $96$ has $12$ divisors, and every divisor other than $1$ and $96$ can be $f_1$ , which gives $10$ .
General $k$ . The $3$ goes into one of the $k$ factors: $k$ choices. The other $k - 1$ factors each need at least one $2$ , so give each of them one. That leaves $5 - (k - 1) = 6 - k$ twos to share freely among all $k$ factors.
Sharing out the leftover $2$ s. Line up the $6 - k$ twos and place $k - 1$ dividers among them to split them into $k$ groups (groups may be empty). That is $(6 - k) + (k - 1) = 5$ symbols in a row, and we choose which $k - 1$ of them are dividers: $\binom{5}{k-1}$ ways.
So for $k$ factors there are $k \times \binom{5}{k-1}$ products.

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

Add. $1 + 10 + 30 + 40 + 25 + 6 = 112$ .

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

Why this works

An ordered product is just a way of sharing prime factors among labeled boxes, with no box left empty. A prime that appears only once, like the $3$ here, fills one box by itself. For the other boxes, hand each one a $2$ first and then share out the rest with the "dividers" count. Splitting by the number of factors keeps the "no empty box" rule easy to handle.

Alternative approach

Build up from smaller numbers by choosing the first factor. If the first factor is $d$ , the rest is an ordered product equal to $96 \div d$ . So $D(n) = 1 +$ the sum of $D(n \div d)$ over all divisors $d$ with $1 < d < n$ . Working upward: $D(2) = 1$ , $D(4) = 2$ , $D(8) = 4$ , $D(16) = 8$ , $D(32) = 16$ , and $D(3) = 1$ , $D(6) = 3$ , $D(12) = 8$ , $D(24) = 20$ , $D(48) = 48$ , $D(96) = 112$ . It is slower, but a good check.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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}$ .

Review in the AoPS books

Intermediate Counting & Probability, Chapter 7: Distributions (§7.2, §7.3)
Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)