Difference between revisions of "2021 AMC 12A Problems/Problem 25"
MRENTHUSIASM (talk | contribs) m (Undo revision 162430 by Renrenthehamster (talk) As a convention of the AoPS Wiki, please keep all video solutions to the end. Thanks.) (Tag: Undo) |
|||
(38 intermediate revisions by 4 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)== |
− | + | 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 | + | 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} |
− | \boldsymbol{p_i} & \boldsymbol{e_i} & \boldsymbol{(e_i+1)^3 | + | & & & & \\ [-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] |
− | + | \hline\hline | |
− | + | & & & & \\ [-2ex] | |
− | + | 1 & 2 & 0 & 1 & \\ | |
− | + | & & 1 & 4 & \\ | |
− | + | & & 2 & 27/4 &\\ | |
− | \hline | + | & & 3 & 8 & \checkmark\\ |
− | + | & & 4 & 125/16 & \\ [0.5ex] | |
− | + | \hline | |
− | + | & & & & \\ [-2ex] | |
− | + | 2 & 3 & 0 & 1 &\\ | |
− | \hline | + | & & 1 & 8/3 & \\ |
− | + | & & 2 & 3 & \checkmark\\ | |
− | + | & & 3 & 64/27 & \\ [0.5ex] | |
− | + | \hline | |
− | \hline | + | & & & & \\ [-2ex] |
− | + | 3 & 5 & 0 & 1 & \\ | |
− | + | & & 1 & 8/5 & \checkmark\\ | |
− | + | & & 2 & 27/25 & \\ [0.5ex] | |
− | \hline | + | \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}</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> | ||
− | + | 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. | |
− | |||
− | |||
~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 62: | Line 76: | ||
== Video Solutions == | == Video Solutions == | ||
https://www.youtube.com/watch?v=gWaUNz0gLE0 (by Dedekind Cuts) | 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://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 | + | {{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 20:50, 18 September 2021
Contents
Problem
Let denote the number of positive integers that divide , including and . For example, and . (This function is known as the divisor function.) LetThere is a unique positive integer such that for all positive integers . What is the sum of the digits of
Solution 1 (Generalization)
We consider the prime factorization of By the Multiplication Principle, we have Now, we rewrite as As for all positive integers note that if and only if for all positive integers and So, is maximized if and only if is maximized.
For each independent factor with a fixed prime where the denominator grows faster than the numerator, as exponential functions always grow faster than polynomial functions. Therefore, for each prime with we look for the nonnegative integer such that is a relative maximum: Finally, the positive integer we seek is The sum of its digits is
Alternatively, once we notice that is a factor of we can conclude that the sum of the digits of must be a multiple of Only choice is possible.
~MRENTHUSIASM
Solution 2 (Solution 1 but Fewer Notations)
The question statement asks for the value of that maximizes . Let start out at ; we will find what factors to multiply by, in order for to maximize the function.
First, we will find what power of to multiply by. If we multiply by , the numerator of , , will multiply by a factor of ; this is because the number has divisors. The denominator, , will simply multiply by . Therefore, the entire function multiplies by a factor of . We want to find the integer value of that maximizes this value. By inspection, this is . Therefore, we multiply by ; right now, is .
Next, we will find what power of to multiply by. Similar to the previous step, we wish to find the integer value of that maximizes . This value, also by inspection, is .
We can repeat this step on the rest of the primes to get but from on, will maximize the value of the function, so the prime is not a factor in . We evaluate to be , so the answer is .
Solution 3 (Fast)
Using the answer choices to our advantage, we can show that must be divisible by 9 without explicitly computing , by exploiting the following fact:
Claim: If is not divisible by 3, then .
Proof: Since is a multiplicative function, we have and . Then Note that the values and do not have to be explicitly computed; we only need the fact that which is easy to show by hand.
The above claim automatically implies is a multiple of 9: if was not divisible by 9, then which is a contradiction, and if was divisible by 3 and not 9, then , also a contradiction. Then the sum of digits of must be a multiple of 9, so only choice 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.