Difference between revisions of "2021 AMC 12A Problems/Problem 25"

Revision as of 07:38, 14 February 2021

Problem

Let $d(n)$ denote the number of positive integers that divide $n$ , including $1$ and $n$ . For example, $d(1)=1,d(2)=2,$ and $d(12)=6$ . (This function is known as the divisor function.) Let $f(n)=\frac{d(n)}{\sqrt [3]n}.$ There is a unique positive integer $N$ such that $f(N)>f(n)$ for all positive integers $n\ne N$ . What is the sum of the digits of $N?$

$\textbf{(A) }5 \qquad \textbf{(B) }6 \qquad \textbf{(C) }7 \qquad \textbf{(D) }8\qquad \textbf{(E) }9$

Video Solution

https://www.youtube.com/watch?v=gWaUNz0gLE0

Solution 1

Consider the prime factorization $n={p_1}^{e_1}{p_2}^{e_2}{p_3}^{e_3}\cdots{p_k}^{e_k}.$ By the Multiplication Principle, $d(n)=(e_1+1)(e_2+1)(e_3+1)\cdots(e_k+1).$ Now, we rewrite $f(n)$ as $f(n)=\frac{d(n)}{\sqrt [3]n}=\frac{(e_1+1)(e_2+1)(e_3+1)\cdots(e_k+1)}{{p_1}^{{e_1}/3}{p_2}^{{e_2}/3}{p_3}^{{e_3}/3}\cdots{p_k}^{{e_k}/3}}=\left(\frac{e_1+1}{{p_1}^{{e_1}/3}}\right)\left(\frac{e_2+1}{{p_2}^{{e_2}/3}}\right)\left(\frac{e_3+1}{{p_3}^{{e_3}/3}}\right)\cdots\left(\frac{e_k+1}{{p_k}^{{e_k}/3}}\right).$ As $f(n)>0$ for all positive integers $n,$ it follows that for all positive integers $a$ and $b$ , $f(a)>f(b)$ if and only if $f(a)^3>f(b)^3.$ So, $f(n)$ is maximized if and only if $f(n)^3=\left(\frac{(e_1+1)^3}{{p_1}^{e_1}}\right)\left(\frac{(e_2+1)^3}{{p_2}^{e_2}}\right)\left(\frac{(e_3+1)^3}{{p_3}^{e_3}}\right)\cdots\left(\frac{(e_k+1)^3}{{p_k}^{e_k}}\right)$ is maximized.

For every factor $\frac{(e_i+1)^3}{{p_i}^{e_i}}$ with a fixed $p_i$ where $1\leq i\leq k,$ the denominator grows faster than the numerator, as exponential functions grow faster than polynomial functions. For each prime $p_i=2,3,5,7,\cdots,$ we look for the $e_i$ for which $\frac{(e_i+1)^3}{{p_i}^{e_i}}$ is a relative maximum: $\begin{array}{ c c c c } p_i & e_i & (e_i+1)^3/\left({p_i}^{e_i}\right) & \text{max?} \\ \hline\hline 2 & 0 & 1 & \\ 2 & 1 & 4 & \\ 2 & 2 & 27/4 &\\ 2 & 3 & 8 & \text{yes}\\ 2 & 4 & 125/16 & \\ \hline 3 & 0 & 1 &\\ 3 & 1 & 8/3 & \\ 3 & 2 & 3 & \text{yes}\\ 3 & 3 & 64/27 & \\ \hline 5 & 0 & 1 & \\ 5 & 1 & 8/5 & \text{yes}\\ 5 & 2 & 27/25 & \\ \hline 7 & 0 & 1 & \\ 7 & 1 & 8/7 & \text{yes}\\ 7 & 2 & 27/49 & \\ \hline 11 & 0 & 1 & \text{yes} \\ 11 & 1 & 8/11 & \\ \hline \cdots & \cdots & \cdots & \end{array}$

Finally, the number we seek is $N=2^3 3^2 5^1 7^1 = 2520.$ The sum of its digits is $2+5+2+0=\boxed{\textbf{(E) }9}.$

Actually, once we get that $3^2$ is a factor of $N,$ we know that the sum of the digits of $N$ must be a multiple of $9.$ Only choice $\textbf{(E)}$ is possible.

~MRENTHUSIASM

Solution 2 (Fast)

Using the answer choices to our advantage, we can show that $N$ must be divisible by 9 without explicitly computing $N$ , by exploiting the following fact:

Claim: If $n$ is not divisible by 3, then $f(9n) > f(3n) > f(n)$ .

Proof: Since $d(\cdot)$ is a multiplicative function, we have $d(3n) = d(3)d(n) = 2d(n)$ and $d(9n) = 3d(n)$ . Then

$\begin{align*} f(3n) &= \frac{2d(n)}{\sqrt[3]{3n}} \approx 1.38 f(n)\\ f(9n) &= \frac{3d(n)}{\sqrt[3]{9n}} \approx 1.44 f(n) \end{align*}$ Note that the values $\frac{2}{\sqrt[3]{3}}$ and $\frac{3}{\sqrt[3]{9}}$ do not have to be explicitly computed; we only need the fact that $\frac{3}{\sqrt[3]{9}} > \frac{2}{\sqrt[3]{3}} > 1$ which is easy to show by hand.

The above claim automatically implies $N$ is a multiple of 9: if $N$ was not divisible by 9, then $f(9N) > f(N)$ which is a contradiction, and if $N$ was divisible by 3 and not 9, then $f(3N) > f(N) > f\left(\frac{N}{3}\right)$ , also a contradiction. Then the sum of digits of $N$ must be a multiple of 9, so only choice $\boxed{\textbf{(E) } 9}$ works.

-scrabbler94

Video Solution by OmegaLearn (Multiplicative function properties + Meta-solving )

https://youtu.be/6P-0ZHAaC_A

~ pi_is_3.14

@@ Line 3: / Line 3: @@
 <math>\textbf{(A) }5 \qquad \textbf{(B) }6 \qquad \textbf{(C) }7 \qquad \textbf{(D) }8\qquad \textbf{(E) }9</math>
+== Video Solution ==
+https://www.youtube.com/watch?v=gWaUNz0gLE0
 ==Solution 1==

2021 AMC 12A (Problems • Answer Key • Resources)
Preceded by Problem 24	Followed by Last problem
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search