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 3 (Only Use If Low On Time))
Line 4: Line 4:
 
<math>\textbf{(A) }5 \qquad \textbf{(B) }6 \qquad \textbf{(C) }7 \qquad \textbf{(D) }8\qquad \textbf{(E) }9</math>
 
<math>\textbf{(A) }5 \qquad \textbf{(B) }6 \qquad \textbf{(C) }7 \qquad \textbf{(D) }8\qquad \textbf{(E) }9</math>
  
−
==Solution==
+
==Solution 1==
−
===Solution 1===
 
 
Consider the prime factorization <cmath>n={p_1}^{e_1}{p_2}^{e_2}{p_3}^{e_3}\cdots{p_k}^{e_k}.</cmath> By the Multiplication Principle, <cmath>d(n)=(e_1+1)(e_2+1)(e_3+1)\cdots(e_k+1).</cmath> Now, we rewrite <math>f(n)</math> as <cmath>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).</cmath> As <math>f(n)>0</math> for all positive integers <math>n,</math> it follows that for all positive integers <math>a</math> and <math>b</math>, <math>f(a)>f(b)</math> if and only if <math>f(a)^3>f(b)^3.</math> So, <math>f(n)</math> is maximized if and only if <cmath>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)</cmath> is maximized.
 
Consider the prime factorization <cmath>n={p_1}^{e_1}{p_2}^{e_2}{p_3}^{e_3}\cdots{p_k}^{e_k}.</cmath> By the Multiplication Principle, <cmath>d(n)=(e_1+1)(e_2+1)(e_3+1)\cdots(e_k+1).</cmath> Now, we rewrite <math>f(n)</math> as <cmath>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).</cmath> As <math>f(n)>0</math> for all positive integers <math>n,</math> it follows that for all positive integers <math>a</math> and <math>b</math>, <math>f(a)>f(b)</math> if and only if <math>f(a)^3>f(b)^3.</math> So, <math>f(n)</math> is maximized if and only if <cmath>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)</cmath> is maximized.
  
Line 41: Line 40:
 
~MRENTHUSIASM
 
~MRENTHUSIASM
  
−
===Solution 2===
+
==Solution 2==
 
A cube root seems bad, so we should just cube it. It seems that if the number is a multiple of 3, there are only two choices. If the number is a multiple of 9, there is one choice. We can prove that for all k is indivisible by 3, f(9k) > f(3k) > f(k). The divisors of 3k contain the divisors of k and the divisors of k multiplied by 3. The divisors of 9k contain the divisors of k, the divisors of k multiplied by 3, and the divisors of k multiplied by 9. <cmath>\frac{27}{9}d(k)^3 > \frac{8}{3}d(k)^3 > d(k)^3</cmath> so <math>f(9k) > f(3k) > f(k)</math> and since <math>\boxed{\textbf{(E) }9}</math> is the only possible answer choice, it is the answer.
 
A cube root seems bad, so we should just cube it. It seems that if the number is a multiple of 3, there are only two choices. If the number is a multiple of 9, there is one choice. We can prove that for all k is indivisible by 3, f(9k) > f(3k) > f(k). The divisors of 3k contain the divisors of k and the divisors of k multiplied by 3. The divisors of 9k contain the divisors of k, the divisors of k multiplied by 3, and the divisors of k multiplied by 9. <cmath>\frac{27}{9}d(k)^3 > \frac{8}{3}d(k)^3 > d(k)^3</cmath> so <math>f(9k) > f(3k) > f(k)</math> and since <math>\boxed{\textbf{(E) }9}</math> is the only possible answer choice, it is the answer.
  

Revision as of 16:59, 12 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$

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{tabular}{ c c c c } pi & ei & fraction & choose? \\ \hline 2 & 0 & 1 & \\ 2 & 1 & 4 & \\ 2 & 2 & 27/4 &\\ 2 & 3 & 8 & yes\\ 2 & 4 & 125/16 & \\ \hline 3 & 0 & 1 &\\ 3 & 1 & 8/3 & \\ 3 & 2 & 3 & yes\\ 3 & 3 & 64/27 & \\ \hline 5 & 0 & 1 & \\ 5 & 1 & 8/5 & yes\\ 5 & 2 & 27/25 & \\ \hline 7 & 0 & 1 & \\ 7 & 1 & 8/7 & yes\\ 7 & 2 & 27/49 & \\ \hline 11 & 0 & 1 & yes \\ 11 & 1 & 8/11 & \\ \hline ,,, & ... & ... & \end{tabular}\]

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

~MRENTHUSIASM

Solution 2

A cube root seems bad, so we should just cube it. It seems that if the number is a multiple of 3, there are only two choices. If the number is a multiple of 9, there is one choice. We can prove that for all k is indivisible by 3, f(9k) > f(3k) > f(k). The divisors of 3k contain the divisors of k and the divisors of k multiplied by 3. The divisors of 9k contain the divisors of k, the divisors of k multiplied by 3, and the divisors of k multiplied by 9. \[\frac{27}{9}d(k)^3 > \frac{8}{3}d(k)^3 > d(k)^3\] so $f(9k) > f(3k) > f(k)$ and since $\boxed{\textbf{(E) }9}$ is the only possible answer choice, it is the answer.

Solution 3 (Only Use If Low On Time)

We can guess that $N$ would be divisible by $9$. Recall, for a number to be divisible by $9$, the sum of its digits must also be divisible by $9$. Since there's only one choice where it's divisible by $9$, we get $\boxed{\textbf{(E)} ~9}$ as our answer. ~rocketsri

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

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

~ 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=146189"