Maths Olympiad Prep

Library / /20 of 31

Algebra Difficulty 6.6 National Olympiad Prove it South Africa

Let f:NN0f: \mathbb{N} \to \mathbb{N}_0 be a function that satisfies
f(mn)=mf(n)+nf(m) f(mn) = mf(n) + nf(m)
for all positive integers m,nm, n and f(2024)=10120f(2024) = 10120.
Prove that there are two integers m,nm, n with mnm \neq n such that f(m)=f(n)f(m) = f(n).

Solution

By setting n=1n = 1, we obtain mf(1)=0mf(1) = 0 for all mm, so f(1)=0f(1) = 0. Next we notice that since every positive integer can be written as a product of prime numbers, the function ff is determined completely by its value on the primes. If there exists m2m \ge 2 such that f(m)=0f(m) = 0, then f(m)=f(1)f(m) = f(1) and we are done. Thus assume for all m2m \ge 2 that f(m)1f(m) \ge 1.
Thus
f(2024)=f(81123)=23f(811)+88f(23)=23(11f(8)+8f(11))+88f(23)=253f(8)+184f(11)+88f(23). \begin{aligned} f(2024) &= f(8 \cdot 11 \cdot 23) = 23f(8 \cdot 11) + 88f(23) = 23(11f(8) + 8f(11)) + 88f(23) \\ &= 253f(8) + 184f(11) + 88f(23). \end{aligned}
To study f(8)f(8), we instead derive a general formula for perfect powers:
f(a2)=af(a)+af(a)=2af(a), f(a^2) = af(a) + af(a) = 2af(a),
f(a3)=a2f(a)+af(a2)=3a2f(a). f(a^3) = a^2f(a) + af(a^2) = 3a^2f(a).
We assume as inductive hypothesis that
f(an)=nan1f(a), f(a^n) = na^{n-1}f(a),
and prove it for n+1n+1 by
f(an+1)=f(ana)=af(an)+anf(a)=a(nan1)f(a)+anf(a)=(n+1)anf(a). f(a^{n+1}) = f(a^n \cdot a) = af(a^n) + a^n f(a) = a(na^{n-1})f(a) + a^n f(a) = (n+1)a^n f(a).
Thus
10120=f(2024)=253(322)f(2)+184f(11)+88f(23)=3036f(2)+184f(11)+88f(23).(1) 10120 = f(2024) = 253(3 \cdot 2^2)f(2) + 184f(11) + 88f(23) = 3036f(2) + 184f(11) + 88f(23). \quad (1)
Considering this equation modulo 11, we conclude that f(11)f(11) is divisible by 11, and by the assumption that f(11)1f(11) \ge 1, we conclude that f(11)11f(11) \ge 11. Similarly, working modulo 23 tells us that f(23)f(23) is divisible by 23 and thus f(23)23f(23) \ge 23. Finally, working modulo 8 tells us that 4f(2)4f(2) is divisible by 8, so f(2)2f(2) \ge 2. Thus the right hand-side of (1) is greater than or equal to
30362+18411+8823=10120. 3036 \cdot 2 + 184 \cdot 11 + 88 \cdot 23 = 10120.
Since we have equality, we must conclude that
f(2)=2,f(11)=11andf(23)=23. f(2) = 2, \quad f(11) = 11 \quad \text{and} \quad f(23) = 23.
Our only hope to find two integers mm and nn for which f(m)=f(n)f(m) = f(n) is to use the information just obtained. Thus, we set
m=2a11b23cn=2d11e23f. m = 2^a 11^b 23^c \quad n = 2^d 11^e 23^f.
Intuitively we hope to find values of d, e, f that are close to a, b, c (e.g. differ by 1) and then solve for values a, b, c that happen to work. We notice that 211=222 \cdot 11 = 22 is close to 23, so let us study
f(22a23c)=23cf(22a)+22af(23c)=23c(a22a1f(22))+22a(c23c1f(23))=23c(a22a1(2f(11)+11f(2)))+22a(c23c123)=23c(a22a144)+22a(c23c123)=(2a+c)22a23c \begin{align*} f(22^a 23^c) &= 23^c f(22^a) + 22^a f(23^c) \\ &= 23^c (a \cdot 22^{a-1} \cdot f(22)) + 22^a (c \cdot 23^{c-1} \cdot f(23)) \\ &= 23^c (a \cdot 22^{a-1} \cdot (2f(11) + 11f(2))) + 22^a (c \cdot 23^{c-1} \cdot 23) \\ &= 23^c (a \cdot 22^{a-1} \cdot 44) + 22^a (c \cdot 23^{c-1} \cdot 23) \\ &= (2a + c) 22^a 23^c \end{align*}
Now we compare f(22a23b+1)f(22^a 23^{b+1}) with f(22a+123b)f(22^{a+1} 23^b) and hope to find values of a, b for which they are equal.
f(22a23b+1)=(2a+b+1)22a23b+1,f(22a+123b)=(2(a+1)+b)22a+123b. \begin{aligned} f(22^a 23^{b+1}) &= (2a + b + 1) 22^a 23^{b+1}, \\ f(22^{a+1} 23^b) &= (2(a + 1) + b) 22^{a+1} 23^b. \end{aligned}
Thus if we can find values of a, b such that
2a+b+1=22and2a+b+2=23 2a + b + 1 = 22 \quad \text{and} \quad 2a + b + 2 = 23
we would be done. Luckily there are many such pairs, for example
(a,b){(1,19),(2,17),(3,15),(4,13),(5,11),(6,9),(7,7),(8,5),(9,3),(10,1)}(\mathbf{a}, \mathbf{b}) \in \{(1, 19), (2, 17), (3, 15), (4, 13), (5, 11), (6, 9), (7, 7), (8, 5), (9, 3), (10, 1)\}.

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.