Problem:
Let be a function from to the positive integers such that for all . If is the number of positive divisors of , compute the minimum possible value of .
Proposed by: Sheldon Kieren Tan
, 2022
Solution
Solution:
Let . We claim that the possible values of are the multiples of . If we can prove this, we will be done, since the minimum value of will be the number of divisors of , which has factors.
First let's construct such an . For any positive integer , I claim that works. Indeed, for any , we find that is divisible by , since . Thus the condition is satisfied.
Now let's prove that must be a multiple of . Take any prime , and let be the largest power of at most . If , we know that , meaning that . Then, using the fact that , we find that , implying that
Now suppose . Then , so . Then, since , we find that . Since , we are done.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.