Difference between revisions of "2021 AMC 12A Problems/Problem 25"
(→Solution 1) |
(→Solution 1) |
||
| Line 10: | Line 10: | ||
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 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: | ||
<cmath>\begin{tabular}{ c c c c } | <cmath>\begin{tabular}{ c c c c } | ||
| − | + | pi & ei & fraction & choose? \\ | |
\hline | \hline | ||
2 & 0 & 1 & \\ | 2 & 0 & 1 & \\ | ||
Revision as of 12:57, 12 February 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.) Let![\[f(n)=\frac{d(n)}{\sqrt [3]n}.\]](http://latex.artofproblemsolving.com/4/1/e/41e0a31875f03c4b386a006e694adbb03555a964.png)
There is a unique positive integer 
such that 
for all positive integers 
. What is the sum of the digits of 
Solution
Solution 1
Consider the prime factorization ![\[n={p_1}^{e_1}{p_2}^{e_2}{p_3}^{e_3}\cdots{p_k}^{e_k}.\]](http://latex.artofproblemsolving.com/0/2/2/02247f7e822bc5f80d6a82939a9047bf02630a00.png)
By the Multiplication Principle, ![\[d(n)=(e_1+1)(e_2+1)(e_3+1)\cdots(e_k+1).\]](http://latex.artofproblemsolving.com/0/d/b/0db5805acd68b9b19093cfe30482b7e22ddde635.png)
Now, we rewrite 
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).\]](http://latex.artofproblemsolving.com/5/b/4/5b4d4480f3ffba0cfa260e995df5d05398f38663.png)
As 
for all positive integers 
it follows that for all positive integers 
and 
, 
if and only if 
So, 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)\]](http://latex.artofproblemsolving.com/d/5/f/d5fbc911692b3828cb409d7ac4c2cb5c06c1fdbf.png)
is maximized.
For every factor 
with a fixed 
where 
the denominator grows faster than the numerator, as exponential functions grow faster than polynomial functions. For each prime 
we look for the 
for which 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}\]](http://latex.artofproblemsolving.com/2/0/d/20d6cced1139d3f2f4818c12b7811b8ce8b32ca2.png)
Finally, the number we seek is 
The sum of its digits is 
~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 f(9k) > f(k) given that k is indivisible by 3. 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\]](http://latex.artofproblemsolving.com/a/1/9/a198261d62ef3e10ba6d2d9017ef2d844e0f6e23.png)
so 
and since 
is the only possible answer choice, it is the answer.
Video Solution by OmegaLearn (Multiplicative function properties + Meta-solving )
~ 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. 
