Skip to main content

2020 AMC 12B Problem 24

Problem 24 of 25HarderNumber TheoryCombinatorics

Let D(n)D(n) denote the number of ways of writing the positive integer nn as a product n=f1⋅f2⋯fk,n = f_1 \cdot f_2 \cdots f_k, where k≥1,k \ge 1, the fif_i are integers strictly greater than 1,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 66 can be written as 6,6, 2⋅3,2 \cdot 3, and 3⋅2,3 \cdot 2, so D(6)=3.D(6) = 3. What is D(96)?D(96)?

Answer choices

Show solution

Solution

The first factor f1f_1 can be any divisor d>1,d \gt 1, after which the rest is an ordered factorization of nd.\frac{n}{d}. So D(n)=∑d∣n, d>1D(nd),D(n) = \sum_{d \mid n,\, d \gt 1} D(\frac{n}{d}), with D(1)=1.D(1) = 1. Computing over the divisors of 96=25⋅3:96 = 2^5\cdot 3: D(2)=D(3)=1,D(2) = D(3) = 1, D(4)=2,D(4) = 2, D(6)=3,D(6) = 3, D(8)=4,D(8) = 4, D(12)=8,D(12) = 8, D(16)=8,D(16) = 8, D(24)=20,D(24) = 20, D(32)=16,D(32) = 16, D(48)=48.D(48) = 48. Finally D(96)=D(48)+D(32)+D(24)+D(16)+D(12)+D(8)+D(6)+D(4)+D(3)+D(2)+D(1)=48+16+20+8+8+4+3+2+1+1+1=112. \begin{gathered} D(96) = D(48) + D(32) \\ {}+ D(24) + D(16) + D(12) \\ {}+ D(8) + D(6) + D(4) \\ {}+ D(3) + D(2) + D(1) \\ = 48 + 16 + 20 + 8 \\ {}+ 8 + 4 + 3 + 2 \\ {}+ 1 + 1 + 1 = 112. \end{gathered} Thus, the correct answer is A.
AoPS wiki

Tagged: recursive counting · factor

More practice