Maths Olympiad Prep

Library / /53 of 299

Algebra Difficulty 5.8 AIME, harder Prove it Iran

Find all functions f:NNf : \mathbb{N} \to \mathbb{N} such that for all positive integers mm and nn
f(n)+1400m2n2+f(f(m)). f(n) + 1400m^2 \mid n^2 + f(f(m)).

Solution

Lemma. *There are infinitely many positive integers nn such that*
f(n)n1310. f(n) \geq n^{\frac{13}{10}}.
Proof. Letting (m,n)=(m,f(m))(m,n) = (m,f(m)) to obtain f(f(m))+1400m2f(m)2+f(f(m))f(f(m)) + 1400m^2 \mid f(m)^2 + f(f(m)) yielding f(m)>mf(m) > m. Plugging n=1n=1 to obtain f(1)+1400m21+f(f(m))f(1) + 1400m^2 \mid 1 + f(f(m)) yielding f(f(m))>m2f(f(m)) > m^2. Assume to the contrary that for all but finitely many nn we have f(n)n2f(n) \le n^{\sqrt{2}}. Since f(n)>nf(n) > n we would obtain n2<f(f(n))f(n)2n^2 < f(f(n)) \le f(n)^{\sqrt{2}} yielding f(n)>n2f(n) > n^{\sqrt{2}}, a contradiction. Hence, f(n)>n2>n1310f(n) > n^{\sqrt{2}} > n^{\frac{13}{10}} for infinitely many nn. This completes our proof.

Let us denote the set of such nn by TT. Letting tTt \in T and aa be a fixed positive integer. Plugging (m,n)=(t,1)(m,n) = (t,1), (t,a)(t,a) to obtain t2+A=C(f(t)+1400)t^2 + A = C(f(t) + 1400) and t2+B=D(f(t)+1400a2)t^2 + B = D(f(t) + 1400a^2) for some positive integers C,DC, D whilst A=f(f(1))A = f(f(1)), B=f(f(a))B = f(f(a)). Choose tt such that A,B<t710A, B < t^{\frac{7}{10}} it follows that
1400CD(1a2)(ADBC)=t2(CD). 1400CD(1 - a^2) - (AD - BC) = t^2(C - D).
The left side is O(t710)O(t^{\frac{7}{10}}) while the right side is O(t2)O(t^2) unless C=DC = D. Hence, for all large enough tt, C=DC = D and therefore, C=AB1400(1a2)C = \frac{A-B}{1400(1-a^2)}, f(t)=t2+A1400CCf(t) = \frac{t^2+A-1400C}{C}. Notice that CC is a function of tt hence, CC doesn't depend on aa. Thus changing aa would not change CC. Hence, for all positive integers a,ba, b :
f(f(a))f(f(1))1400(1a2)=f(f(b))f(f(1))1400(1b2). \frac{f(f(a)) - f(f(1))}{1400(1 - a^2)} = \frac{f(f(b)) - f(f(1))}{1400(1 - b^2)}.
Implying that f(f(a))=ra2+sf(f(a)) = ra^2 + s, for some constants r,sr, s. That is,
f(n)+1400m2n2+rm2+s, f(n) + 1400m^2 \mid n^2 + rm^2 + s,
Yielding
f(n)+1400m21400n2rf(n)+1400s. f(n) + 1400m^2 \mid 1400n^2 - rf(n) + 1400s.
Choose mm large enough to obtain that 1400n2rf(n)+1400s=01400n^2 - rf(n) + 1400s = 0. That is,
f(n)=1400n2+1400sr, f(n) = \frac{1400n^2 + 1400s}{r},
But then f(f(n))f(f(n)) must be a polynomial of degree 4 in nn. This contradicts to what we've already obtained. Hence, there is no such a function. ■

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.