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

(Solution 2 (Fast))
m (See also)
 
(49 intermediate revisions by 5 users not shown)
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 1==
+
==Solution 1 (Generalization)==
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.
+
We consider the prime factorization of <math>n:</math> <cmath>n=\prod_{i=1}^{k}p_i^{e_i}.</cmath> By the Multiplication Principle, we have <cmath>d(n)=\prod_{i=1}^{k}(e_i+1).</cmath> Now, we rewrite <math>f(n)</math> as <cmath>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}}.</cmath> As <math>f(n)>0</math> for all positive integers <math>n,</math> note that <math>f(a)>f(b)</math> if and only if <math>f(a)^3>f(b)^3</math> for all positive integers <math>a</math> and <math>b.</math> So, <math>f(n)</math> is maximized if and only if <cmath>f(n)^3=\prod_{i=1}^{k}\frac{(e_i+1)^3}{p_i^{{e_i}}}</cmath> is maximized.
  
For every 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=2,3,5,7,\cdots,</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 each independent factor <math>\frac{(e_i+1)^3}{p_i^{e_i}}</math> with a fixed prime <math>p_i,</math> where <math>1\leq i\leq k,</math> the denominator grows faster than the numerator, as exponential functions always grow faster than polynomial functions. Therefore, for each prime <math>p_i</math> with <math>\left(p_1,p_2,p_3,p_4,\ldots\right)=\left(2,3,5,7,\ldots\right),</math> we look for the nonnegative integer <math>e_i</math> such that <math>\frac{(e_i+1)^3}{p_i^{e_i}}</math> is a relative maximum:
<cmath>\begin{array}{ c c c c }
+
<cmath>\begin{array}{c|c|c|c|c}  
p_i & e_i & (e_i+1)^3/\left({p_i}^{e_i}\right) & \text{max?} \\  
+
& & & & \\ [-2.25ex]
\hline\hline
+
\boldsymbol{i} & \boldsymbol{p_i} & \boldsymbol{e_i} & \boldsymbol{\dfrac{(e_i+1)^3}{p_i^{e_i}}} & \textbf{Max?} \\ [2.5ex]
2 & 0 & 1 & \\
+
\hline\hline  
2 & 1 & 4 & \\
+
& & & & \\ [-2ex]
2 & 2 & 27/4 &\\
+
1 & 2 & 0 & 1 & \\    
2 & 3 & 8 & \text{yes}\\
+
& & 1 & 4 & \\  
2 & 4 & 125/16 & \\
+
& & 2 & 27/4 &\\  
\hline
+
& & 3 & 8 & \checkmark\\  
3 & 0 & 1 &\\
+
& & 4 & 125/16 & \\ [0.5ex]
3 & 1 & 8/3 & \\
+
\hline
3 & 2 & 3 &  \text{yes}\\
+
& & & & \\ [-2ex]
3 & 3 & 64/27 &  \\
+
2 & 3 & 0 & 1 &\\  
\hline
+
& & 1 & 8/3 & \\  
5 & 0 & 1 &  \\
+
& & 2 & 3 &  \checkmark\\  
5 & 1 & 8/5 &  \text{yes}\\
+
& & 3 & 64/27 &  \\ [0.5ex]
5 & 2 & 27/25 & \\
+
\hline
\hline
+
& & & & \\ [-2ex]
7 & 0 & 1 &  \\
+
3 & 5 & 0 & 1 &  \\  
7 & 1 & 8/7 &  \text{yes}\\
+
& & 1 & 8/5 &  \checkmark\\  
7 & 2 & 27/49 & \\
+
& & 2 & 27/25 & \\ [0.5ex]
\hline
+
\hline
11 & 0 & 1 & \text{yes} \\
+
& & & & \\ [-2ex]
11 & 1 & 8/11 &  \\
+
4 & 7 & 0 & 1 &  \\  
\hline
+
& & 1 & 8/7 &  \checkmark\\  
\cdots & \cdots & \cdots &
+
& & 2 & 27/49 & \\ [0.5ex]
 +
\hline
 +
& & & & \\ [-2ex]
 +
\geq5 & \geq11 & 0 & 1 & \checkmark \\  
 +
& & \geq1 & \leq8/11 &   \\ [0.5ex]
 
\end{array}</cmath>
 
\end{array}</cmath>
 +
Finally, the positive integer we seek is <math>N=2^3\cdot3^2\cdot5^1\cdot7^1=2520.</math> The sum of its digits is <math>2+5+2+0=\boxed{\textbf{(E) }9}.</math>
  
Finally, the number we seek is <math>N=2^3 3^2 5^1 7^1 = 2520.</math> The sum of its digits is <math>2+5+2+0=\boxed{\textbf{(E) }9}.</math>
+
Alternatively, once we notice that <math>3^2</math> is a factor of <math>N,</math> we can conclude that the sum of the digits of <math>N</math> must be a multiple of <math>9.</math> Only choice <math>\textbf{(E)}</math> is possible.
  
Actually, once we get that <math>3^2</math> is a factor of <math>N,</math> we know that the sum of the digits of <math>N</math> must be a multiple of <math>9.</math> Only choice <math>\textbf{(E)}</math> is possible.
 
 
 
 
~MRENTHUSIASM
 
~MRENTHUSIASM
  
==Solution 2 (Fast)==
+
==Solution 2 (Solution 1 but Fewer Notations)==
 +
The question statement asks for the value of <math>N</math> that maximizes <math>f(N)</math>. Let <math>N</math> start out at <math>1</math>; we will find what factors to multiply <math>N</math> by, in order for <math>N</math> to maximize the function.
 +
 
 +
First, we will find what power of <math>2</math> to multiply <math>N</math> by. If we multiply <math>N</math> by <math>2^{a}</math>, the numerator of <math>f</math>, <math>d(N)</math>, will multiply by a factor of <math>a+1</math>; this is because the number <math>2^{a}</math> has <math>a+1</math> divisors. The denominator, <math>\sqrt[3]{N}</math>, will simply multiply by <math>\sqrt[3]{2^{a}}</math>. Therefore, the entire function multiplies by a factor of <math>\frac{a+1}{\sqrt[3]{2^{a}}}</math>. We want to find the integer value of <math>a</math> that maximizes this value. By inspection, this is <math>3</math>. Therefore, we multiply <math>N</math> by <math>8</math>; right now, <math>N</math> is <math>8</math>.
 +
 
 +
Next, we will find what power of <math>3</math> to multiply <math>N</math> by. Similar to the previous step, we wish to find the integer value of <math>a</math> that maximizes <math>\frac{a+1}{\sqrt[3]{3^{a}}}</math>. This value, also by inspection, is <math>2</math>.
 +
 
 +
We can repeat this step on the rest of the primes to get
 +
<cmath>N = 2^{3} \cdot 3^{2} \cdot 5 \cdot 7</cmath>
 +
but from <math>11</math> on, <math>a=0</math> will maximize the value of the function, so the prime is not a factor in <math>N</math>.
 +
We evaluate <math>N</math> to be <math>2520</math>, so the answer is <math>\boxed{\textbf{(E) }9}</math>.
 +
 
 +
==Solution 3 (Fast)==
 
Using the answer choices to our advantage, we can show that <math>N</math> must be divisible by 9 without explicitly computing <math>N</math>, by exploiting the following fact:
 
Using the answer choices to our advantage, we can show that <math>N</math> must be divisible by 9 without explicitly computing <math>N</math>, by exploiting the following fact:
  
Line 48: Line 63:
  
 
'''Proof''': Since <math>d(\cdot)</math> is a [[multiplicative function]], we have <math>d(3n) = d(3)d(n) = 2d(n)</math> and <math>d(9n) = 3d(n)</math>. Then
 
'''Proof''': Since <math>d(\cdot)</math> is a [[multiplicative function]], we have <math>d(3n) = d(3)d(n) = 2d(n)</math> and <math>d(9n) = 3d(n)</math>. Then
 
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
 
f(3n) &= \frac{2d(n)}{\sqrt[3]{3n}} \approx 1.38 f(n)\\
 
f(3n) &= \frac{2d(n)}{\sqrt[3]{3n}} \approx 1.38 f(n)\\
Line 60: Line 74:
 
-scrabbler94
 
-scrabbler94
  
== Video Solution by OmegaLearn (Multiplicative function properties + Meta-solving ) ==
+
== Video Solutions ==
https://youtu.be/6P-0ZHAaC_A
+
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)
  
~ pi_is_3.14
+
https://youtu.be/6P-0ZHAaC_A (by OmegaLearn) ~ pi_is_3.14
  
 
==See also==
 
==See also==
{{AMC12 box|year=2021|ab=A|num-b=24|after=Last problem}}
+
{{AMC12 box|year=2021|ab=A|num-b=24|after=Last Problem}}
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 22:18, 11 September 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 (Generalization)

We consider the prime factorization of $n:$ \[n=\prod_{i=1}^{k}p_i^{e_i}.\] By the Multiplication Principle, we have \[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,$ note that $f(a)>f(b)$ if and only if $f(a)^3>f(b)^3$ for all positive integers $a$ and $b.$ 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 each independent factor $\frac{(e_i+1)^3}{p_i^{e_i}}$ with a fixed prime $p_i,$ where $1\leq i\leq k,$ the denominator grows faster than the numerator, as exponential functions always grow faster than polynomial functions. Therefore, for each prime $p_i$ with $\left(p_1,p_2,p_3,p_4,\ldots\right)=\left(2,3,5,7,\ldots\right),$ we look for the nonnegative integer $e_i$ such that $\frac{(e_i+1)^3}{p_i^{e_i}}$ is a relative maximum: \[\begin{array}{c|c|c|c|c}  & & & & \\ [-2.25ex] \boldsymbol{i} & \boldsymbol{p_i} & \boldsymbol{e_i} & \boldsymbol{\dfrac{(e_i+1)^3}{p_i^{e_i}}} & \textbf{Max?} \\ [2.5ex] \hline\hline  & & & & \\ [-2ex] 1 & 2 & 0 & 1 & \\      & & 1 & 4 & \\     & & 2 & 27/4 &\\     & & 3 & 8 & \checkmark\\     & & 4 & 125/16 & \\ [0.5ex] \hline   & & & & \\ [-2ex] 2 & 3 & 0 & 1 &\\     & & 1 & 8/3 & \\     & & 2 & 3 &  \checkmark\\     & & 3 & 64/27 &  \\ [0.5ex] \hline   & & & & \\ [-2ex] 3 & 5 & 0 & 1 &  \\     & & 1 & 8/5 &  \checkmark\\     & & 2 & 27/25 & \\ [0.5ex] \hline   & & & & \\ [-2ex] 4 & 7 & 0 & 1 &  \\     & & 1 & 8/7 &  \checkmark\\     & & 2 & 27/49 & \\ [0.5ex] \hline   & & & & \\ [-2ex] \geq5 & \geq11 & 0 & 1 & \checkmark \\     & & \geq1 & \leq8/11 &   \\ [0.5ex] \end{array}\] Finally, the positive integer 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}.$

Alternatively, 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 (Solution 1 but Fewer Notations)

The question statement asks for the value of $N$ that maximizes $f(N)$. Let $N$ start out at $1$; we will find what factors to multiply $N$ by, in order for $N$ to maximize the function.

First, we will find what power of $2$ to multiply $N$ by. If we multiply $N$ by $2^{a}$, the numerator of $f$, $d(N)$, will multiply by a factor of $a+1$; this is because the number $2^{a}$ has $a+1$ divisors. The denominator, $\sqrt[3]{N}$, will simply multiply by $\sqrt[3]{2^{a}}$. Therefore, the entire function multiplies by a factor of $\frac{a+1}{\sqrt[3]{2^{a}}}$. We want to find the integer value of $a$ that maximizes this value. By inspection, this is $3$. Therefore, we multiply $N$ by $8$; right now, $N$ is $8$.

Next, we will find what power of $3$ to multiply $N$ by. Similar to the previous step, we wish to find the integer value of $a$ that maximizes $\frac{a+1}{\sqrt[3]{3^{a}}}$. This value, also by inspection, is $2$.

We can repeat this step on the rest of the primes to get \[N = 2^{3} \cdot 3^{2} \cdot 5 \cdot 7\] but from $11$ on, $a=0$ will maximize the value of the function, so the prime is not a factor in $N$. We evaluate $N$ to be $2520$, so the answer is $\boxed{\textbf{(E) }9}$.

Solution 3 (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 (ProblemsAnswer KeyResources)
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

Invalid username
Login to AoPS