Maths Olympiad Prep

Library / /1121 of 1394

, 2022

Number theory Difficulty 5.6 AIME, harder Prove it United States

Problem:
Let ff be a function from {1,2,,22}\{1,2, \ldots, 22\} to the positive integers such that mnf(m)+f(n)m n \mid f(m)+f(n) for all m,n{1,2,,22}m, n \in \{1,2, \ldots, 22\}. If dd is the number of positive divisors of f(20)f(20), compute the minimum possible value of dd.
Proposed by: Sheldon Kieren Tan

Solution

Solution:
Let L=lcm(1,2,,22)L=\operatorname{lcm}(1,2, \ldots, 22). We claim that the possible values of f(20)f(20) are the multiples of 20L20 L. If we can prove this, we will be done, since the minimum value of dd will be the number of divisors of 20L=26325271113171920 L=2^{6} \cdot 3^{2} \cdot 5^{2} \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19, which has 73225=20167 \cdot 3^{2} \cdot 2^{5}=2016 factors.

First let's construct such an ff. For any positive integer aa, I claim that f(n)=aLnf(n)=a L n works. Indeed, for any m,nm, n, we find that f(m)=aLmf(m)=a L m is divisible by mnm n, since nLn \mid L. Thus the condition is satisfied.

Now let's prove that f(20)f(20) must be a multiple of 20L20 L. Take any prime pp, and let qq be the largest power of pp at most 2222. If p2p \neq 2, we know that q22f(q)q^{2} \mid 2 f(q), meaning that q2f(q)q^{2} \mid f(q). Then, using the fact that 20qf(q)+f(20)20 q \mid f(q)+f(20), we find that gcd(20q,q2)f(q),f(q)+f(20)\operatorname{gcd}\left(20 q, q^{2}\right) \mid f(q), f(q)+f(20), implying that
νp(f(20))νp(gcd(20q,q2))=νp(20q)=νp(20L) \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=2p=2. Then 28=1622f(16)2^{8}=16^{2} \mid 2 f(16), so 27f(16)2^{7} \mid f(16). Then, since 526=2016f(16)+f(20)5 \cdot 2^{6}=20 \cdot 16 \mid f(16)+f(20), we find that 27f(20)2^{7} \mid f(20). Since 7=ν2(20L)7=\nu_{2}(20 L), 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.