HMMT 二月 2022 · ALGNT 赛 · 第 6 题

HMMT February 2022 — ALGNT Round — Problem 6

Let f be a function from { 1 , 2 , . . . , 22 } to the positive integers such that mn | f ( m ) + f ( n ) for all m, n ∈ { 1 , 2 , . . . , 22 } . If d is the number of positive divisors of f (20), compute the minimum possible value of d .

解析

Let f be a function from { 1 , 2 , . . . , 22 } to the positive integers such that mn | f ( m ) + f ( n ) for all m, n ∈ { 1 , 2 , . . . , 22 } . If d is the number of positive divisors of f (20), compute the minimum possible value of d . Proposed by: Sheldon Kieren Tan Answer: 2016 Solution: Let L = lcm(1 , 2 , . . . , 22). We claim that the possible values of f (20) are the multiples of 20 L . If we can prove this, we will be done, since the minimum value of d will be the number of divisors 6 2 2 2 5 of 20 L = 2 · 3 · 5 · 7 · 11 · 13 · 17 · 19, which has 7 · 3 · 2 = 2016 factors. First let’s construct such an f . For any positive integer a , I claim that f ( n ) = aLn works. Indeed, for any m, n , we find that f ( m ) = aLm is divisible by mn , since n | L . Thus the condition is satisfied. Now let’s prove that f (20) must be a multiple of 20 L . Take any prime p , and let q be the largest power 2 2 of p at most 22. If p ̸ = 2, we know that q | 2 f ( q ), meaning that q | f ( q ). Then, using the fact that 2 20 q | f ( q ) + f (20), we find that gcd(20 q, q ) | f ( q ) , f ( q ) + f (20), implying that 2 ν ( f (20)) ≥ ν (gcd(20 q, q )) = ν (20 q ) = ν (20 L ) . p p p p 8 2 7 6 Now suppose p = 2. Then 2 = 16 | 2 f (16), so 2 | f (16). Then, since 5 · 2 = 20 · 16 | f (16) + f (20), 7 we find that 2 | f (20). Since 7 = ν (20 L ), we are done. 2