Find all functions f:N→N such that for all positive integers m and n f(n)+1400m2∣n2+f(f(m)).
Solution
Lemma. *There are infinitely many positive integers n such that* f(n)≥n1013. Proof. Letting (m,n)=(m,f(m)) to obtain f(f(m))+1400m2∣f(m)2+f(f(m)) yielding f(m)>m. Plugging n=1 to obtain f(1)+1400m2∣1+f(f(m)) yielding f(f(m))>m2. Assume to the contrary that for all but finitely many n we have f(n)≤n2. Since f(n)>n we would obtain n2<f(f(n))≤f(n)2 yielding f(n)>n2, a contradiction. Hence, f(n)>n2>n1013 for infinitely many n. This completes our proof.
Let us denote the set of such n by T. Letting t∈T and a be a fixed positive integer. Plugging (m,n)=(t,1), (t,a) to obtain t2+A=C(f(t)+1400) and t2+B=D(f(t)+1400a2) for some positive integers C,D whilst A=f(f(1)), B=f(f(a)). Choose t such that A,B<t107 it follows that 1400CD(1−a2)−(AD−BC)=t2(C−D). The left side is O(t107) while the right side is O(t2) unless C=D. Hence, for all large enough t, C=D and therefore, C=1400(1−a2)A−B, f(t)=Ct2+A−1400C. Notice that C is a function of t hence, C doesn't depend on a. Thus changing a would not change C. Hence, for all positive integers a,b : 1400(1−a2)f(f(a))−f(f(1))=1400(1−b2)f(f(b))−f(f(1)). Implying that f(f(a))=ra2+s, for some constants r,s. That is, f(n)+1400m2∣n2+rm2+s, Yielding f(n)+1400m2∣1400n2−rf(n)+1400s. Choose m large enough to obtain that 1400n2−rf(n)+1400s=0. That is, f(n)=r1400n2+1400s, But then f(f(n)) must be a polynomial of degree 4 in n. 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.