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
Consider the prime factorization By the Multiplication Principle, Now, we rewrite as As for all positive integers it follows that for all positive integers and , if and only if So, is maximized if and only if 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:
Finally, the number we seek is The sum of its digits is
Actually, once we get that is a factor of we know that the sum of the digits of must be a multiple of Only choice is possible.
Solution 2 (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|