2021 AMC 12A Problems/Problem 25
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
There 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
Solution 4 (Guesswork)
The problem mentions the sum of digits - recall that if a number is divisible by 9, then so is the sum of its digits. Guess that the answer must therefore be .
- youtube.com/indianmathguy
Solution 5
The aim of this problem is to maximize
Let's start with when has one prime factor. If this is the case, let
be its exponent. Clearly,
must be the prime factor because regardless of what prime we use, the numerator will only depend on
, so we must minimize the denominator. Therefore, in this case, we want to maximize
(since the
will have
factors). By inspection, we find that
does the job.
Now notice that we can add another prime factor to . Since we can split up prime factors and multiplication under prime factorization and cube roots, we just need to maximize the same process for the second prime factor. Again, we go with the next least prime factor to minimize the denominator which is
. To clarify, we want to maximize
(letting the exponent be
). Inspection again gives that
is maximal.
We repeat this process two more times, adding a prime factor for and
. We find by inspection that the maximizing power of 5 is
and the maximizing power of 7 is also
.
Now, notice that if , then regardless of what exponent we put in the numerator,
will be less than
. This is bad, because then our maximized value of
will decrease. Noting that our next least prime factor is
, we know that we are done.
We evaluate to be
, so the answer is
.
~xHypotenuse
Video Solutions
https://www.youtube.com/watch?v=gWaUNz0gLE0 (by Dedekind Cuts)
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.