HMMT-Feb 2022 alg, Problem 6

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

Solution: Solution: Let $L=\operatorname{lcm}(1,2, \ldots, 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 of $20 L=2^{6} \cdot 3^{2} \cdot 5^{2} \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19$, which has $7 \cdot 3^{2} \cdot 2^{5}=2016$ factors. First let's construct such an $f$. For any positive integer $a$, I claim that $f(n)=a L n$ works. Indeed, for any $m, n$, we find that $f(m)=a L m$ is divisible by $m n$, since $n \mid 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 of $p$ at most 22. If $p \neq 2$, we know that $q^{2} \mid 2 f(q)$, meaning that $q^{2} \mid f(q)$. Then, using the fact that $20 q \mid f(q)+f(20)$, we find that $\operatorname{gcd}\left(20 q, q^{2}\right) \mid f(q), f(q)+f(20)$, implying that \[ \nu_{p}(f(20)) \geq \nu_{p}\left(\operatorname{gcd}\left(20 q, q^{2}\right)\right)=\nu_{p}(20 q)=\nu_{p}(20 L) \] Now suppose $p=2$. Then $2^{8}=16^{2} \mid 2 f(16)$, so $2^{7} \mid f(16)$. Then, since $5 \cdot 2^{6}=20 \cdot 16 \mid f(16)+f(20)$, we find that $2^{7} \mid f(20)$. Since $7=\nu_{2}(20 L)$, we are done. $\fbox{2016}$.

Answer: 2016