Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Solution 1)
m (→‎Solution 1)
Line 9: Line 9:
 
For every independent factor <math>\frac{(e_i+1)^3}{p_i^{e_i}}</math> with a fixed <math>p_i,</math> where <math>1\leq i\leq k,</math> the denominator grows faster than the numerator, as exponential functions grow faster than polynomial functions. For each prime <math>p_i</math> with <math>\left(p_1,p_2,p_3,p_4,\cdots\right)=\left(2,3,5,7,\cdots\right),</math> we look for the <math>e_i</math> for which <math>\frac{(e_i+1)^3}{p_i^{e_i}}</math> is a relative maximum:
 
For every independent factor <math>\frac{(e_i+1)^3}{p_i^{e_i}}</math> with a fixed <math>p_i,</math> where <math>1\leq i\leq k,</math> the denominator grows faster than the numerator, as exponential functions grow faster than polynomial functions. For each prime <math>p_i</math> with <math>\left(p_1,p_2,p_3,p_4,\cdots\right)=\left(2,3,5,7,\cdots\right),</math> we look for the <math>e_i</math> for which <math>\frac{(e_i+1)^3}{p_i^{e_i}}</math> is a relative maximum:
 
<cmath>\begin{array}{c|c|c|c|c}  
 
<cmath>\begin{array}{c|c|c|c|c}  
−
& & & & \\ [-3ex]
+
& & & & \\ [-2.5ex]
 
\boldsymbol{i} & \boldsymbol{p_i} & \boldsymbol{e_i} & \boldsymbol{(e_i+1)^3/\left(p_i^{e_i}\right)} & \textbf{max?} \\ [0.5ex]
 
\boldsymbol{i} & \boldsymbol{p_i} & \boldsymbol{e_i} & \boldsymbol{(e_i+1)^3/\left(p_i^{e_i}\right)} & \textbf{max?} \\ [0.5ex]
 
\hline\hline  
 
\hline\hline  

Revision as of 17:04, 22 March 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$

Solution 1

Consider the prime factorization \[n=\prod_{i=1}^{k}p_i^{e_i}.\] By the Multiplication Principle, \[d(n)=\prod_{i=1}^{k}(e_i+1).\] Now, we rewrite $f(n)$ as \[f(n)=\frac{d(n)}{\sqrt [3]n}=\frac{\prod_{i=1}^{k}(e_i+1)}{\prod_{i=1}^{k}p_i^{e_i/3}}=\prod_{i=1}^{k}\frac{e_i+1}{p_i^{{e_i}/3}}.\] 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=\prod_{i=1}^{k}\frac{(e_i+1)^3}{p_i^{{e_i}}}\] is maximized.

For every independent 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$ with $\left(p_1,p_2,p_3,p_4,\cdots\right)=\left(2,3,5,7,\cdots\right),$ 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|c} & & & & \\ [-2.5ex] \boldsymbol{i} & \boldsymbol{p_i} & \boldsymbol{e_i} & \boldsymbol{(e_i+1)^3/\left(p_i^{e_i}\right)} & \textbf{max?} \\ [0.5ex] \hline\hline & & & & \\ [-2ex] 1 & 2 & 0 & 1 & \\ & & 1 & 4 & \\ & & 2 & 27/4 &\\ & & 3 & 8 & \text{yes}\\ & & 4 & 125/16 & \\ [0.5ex] \hline & & & & \\ [-2ex] 2 & 3 & 0 & 1 &\\ & & 1 & 8/3 & \\ & & 2 & 3 & \text{yes}\\ & & 3 & 64/27 & \\ [0.5ex] \hline & & & & \\ [-2ex] 3 & 5 & 0 & 1 & \\ & & 1 & 8/5 & \text{yes}\\ & & 2 & 27/25 & \\ [0.5ex] \hline & & & & \\ [-2ex] 4 & 7 & 0 & 1 & \\ & & 1 & 8/7 & \text{yes}\\ & & 2 & 27/49 & \\ [0.5ex] \hline & & & & \\ [-2ex] \geq5 & \geq11 & 0 & 1 & \text{yes} \\ & & \geq1 & \leq8/11 & \\ [0.5ex] \end{array}\]

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

Actually, once we notice that $3^2$ is a factor of $N,$ we can conclude 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 Solutions

https://www.youtube.com/watch?v=gWaUNz0gLE0 (by Dedekind Cuts)

https://www.youtube.com/watch?v=Sv4gj1vMjOs (by Aaron He)

https://youtube.com/watch?v=y_7s8fvMCdI (by Punxsutawney Phil)

https://youtu.be/6P-0ZHAaC_A (by OmegaLearn)


~ pi_is_3.14

See also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AMC_12A_Problems/Problem_25&oldid=149782"