AMC12 2020 B

AMC12 2020 B · Q24

AMC12 2020 B · Q24. It mainly tests Primes & prime factorization, Counting divisors.

Let $D(n)$ denote the number of ways of writing the positive integer $n$ as a product $$n = f_1 \cdot f_2 \cdot \cdots \cdot f_k,$$ where $k \geq 1$, 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 \cdot 2$, so $D(6) = 3$. What is $D(96)$?

令 $D(n)$ 表示将正整数 $n$ 表示为 $$n = f_1 \cdot f_2 \cdot \cdots \cdot f_k,$$ 的表示方法个数，其中 $k \geq 1$，$f_i$ 是严格大于 $1$ 的整数，且因子列出的顺序重要（即仅因子顺序不同的两种表示视为不同）。例如，$6$ 可以写成 $6$、$2 \cdot 3$ 和 $3 \cdot 2$，所以 $D(6) = 3$。$D(96)$ 是多少？

(A) 112 112

(B) 128 128

(D) 172 172

(E) 184 184

Answer

Correct choice: (A)

正确答案：（A）

Solution

Answer (A): Clearly $D(1)=0$. Suppose $n>1$. The first factor $f_1$ in a representation is a divisor of $n$ with $f_1>1$. If $f_1=n$, then there is a representation with just one factor. Suppose that $f_1$ is a divisor of $n$ and $1<f_1<n$. Then the further factors after $f_1$ are exactly the representations of $\frac{n}{f_1}$. This gives a recurrence relation: If $n>1$, then \[ D(n)=1+\sum_{\substack{f\mid n\\1<f<n}} D\!\left(\frac{n}{f}\right). \] Thus a table of values of $D(2^j3^k)$ can be constructed for $j=0,1,\ldots,5$, $k=0,1$. \[ \begin{array}{c|cc} j\backslash k & 0 & 1\\ \hline 0 & 0 & 1\\ 1 & 1 & 3\\ 2 & 2 & 8\\ 3 & 4 & 20\\ 4 & 8 & 48\\ 5 & 16 & 112 \end{array} \] From the table, it can be seen that $D(96)=112$.

答案（A）：显然 $D(1)=0$。设 $n>1$。一个表示中的第一个因子 $f_1$ 是 $n$ 的一个除数，且 $f_1>1$。若 $f_1=n$，则存在只有一个因子的表示。设 $f_1$ 是 $n$ 的除数并且 $1<f_1<n$。那么在 $f_1$ 之后的其余因子恰好对应于 $\frac{n}{f_1}$ 的各种表示。因此得到递推关系：若 $n>1$，则 \[ D(n)=1+\sum_{\substack{f\mid n\\1<f<n}} D\!\left(\frac{n}{f}\right). \] 因此可以为 $j=0,1,\ldots,5$、$k=0,1$ 构造 $D(2^j3^k)$ 的取值表。 \[ \begin{array}{c|cc} j\backslash k & 0 & 1\\ \hline 0 & 0 & 1\\ 1 & 1 & 3\\ 2 & 2 & 8\\ 3 & 4 & 20\\ 4 & 8 & 48\\ 5 & 16 & 112 \end{array} \] 由表可见 $D(96)=112$。

Topics