Maths Olympiad Prep

Library / /20 of 46

, 2022

Algebra Difficulty 6.0 AIME, harder Prove it Japan

Let NN be the set of positive integers. Determine all functions f:NNf : N \to N such that, for all positive integers mm and nn,
ff(n)(m)+mn=f(m)f(n). f^{f(n)}(m) + mn = f(m)f(n).
Note that fk(n)=f(f(f(n)))k timesf^k(n) = \underbrace{f(f(\cdots f(n)\cdots))}_{k \text{ times}}.

Solution

Let \ell be a positive integer. By substituting (m,n)=(f(),)(m, n) = (f(\ell), \ell) and (,f())(\ell, f(\ell)) into the original equation and comparing them, we obtain
ff()+1()+f()=f()f(f())=ff(f())()+f(), f^{f(\ell)+1}(\ell) + \ell f(\ell) = f(\ell)f(f(\ell)) = f^{f(f(\ell))}(\ell) + \ell f(\ell),
or ff()+1()=ff(f())()f^{f(\ell)+1}(\ell) = f^{f(f(\ell))}(\ell).
Letting m=nm = n in the original equation yield f(n)2=n2+ff(n)(n)>n2f(n)^2 = n^2 + f^{f(n)}(n) > n^2, or f(n)>nf(n) > n. Hence, fk+1(n)=f(fk(n))>fk(n)f^{k+1}(n) = f(f^k(n)) > f^k(n) for any positive integer kk, which leads to
f(n)<f2(n)<f3(n)< f(n) < f^2(n) < f^3(n) < \dots
In particular, if fs(n)=ft(n)f^s(n) = f^t(n) for some positive integers s,ts, t, then s=ts = t. Combined with ff()+1()=ff(f())()f^{f(\ell)+1}(\ell) = f^{f(f(\ell))}(\ell), we obtain f(f())=f()+1f(f(\ell)) = f(\ell) + 1.

In particular, by letting k=f(n)k = f(n) in the above statement, ff(n)(n)=f(n)+f(n)1=2f(n)1f^{f(n)}(n) = f(n) + f(n) - 1 = 2f(n) - 1. We also have f(n)2=n2+ff(n)(n)f(n)^2 = n^2 + f^{f(n)}(n) (see the second paragraph), and we deduce (f(n)1)2=n2(f(n) - 1)^2 = n^2. Since f(n)10f(n) - 1 \ge 0, it implies f(n)1=nf(n) - 1 = n, or f(n)=n+1f(n) = n + 1.
We conclude the proof by checking f(n)=n+1f(n) = n + 1 satisfies the original equation. The left side of the equation is ff(n)(m)+mn=m+f(n)+mn=mn+m+n+1f^{f(n)}(m) + mn = m + f(n) + mn = mn + m + n + 1; the right is f(m)f(n)=(m+1)(n+1)=mn+m+n+1f(m)f(n) = (m+1)(n+1) = mn + m + n + 1. Therefore, the answer is f(n)=n+1f(n) = n + 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.