2021 AMC 12A Problems/Problem 25
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
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
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.
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.
|2021 AMC 12A (Problems • Answer Key • Resources)|
|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|