International Mathematical Olympiad Shortlisted Problems

Answer. $f(n)=n$.

Solution 1. Setting $m=n=2$ tells us that $4+f(2)\mid 2f(2)+2$. Since $2f(2)+2<2(4+f(2))$, we must have $2f(2)+2=4+f(2)$, so $f(2)=2$. Plugging in $m=2$ then tells us that $4+f(n)\mid 4+n$, which implies that $f(n)⩽n$ for all $n$. Setting $m=n$ gives $n^2+f(n)\mid nf(n)+n$, so $nf(n)+n⩾n^2+f(n)$ which we rewrite as $(n-1)(f(n)-n)⩾0$. Therefore $f(n)⩾n$ for all $n⩾2$. This is trivially true for $n=1$ also. It follows that $f(n)=n$ for all $n$. This function obviously satisfies the desired property.

Solution 2. Setting $m=f(n)$ we get $f(n)(f(n)+1)\mid f(n)f(f(n))+n$. This implies that $f(n)\mid n$ for all $n$. Now let $m$ be any positive integer, and let $p>2m^2$ be a prime number. Note that $p>mf(m)$ also. Plugging in $n=p-mf(m)$ we learn that $m^2+f(n)$ divides $p$. Since $m^2+f(n)$ cannot equal 1, it must equal $p$. Therefore $p-m^2=f(n)\mid n=p-mf(m)$. But $p-mf(m)<p<2\left(p-m^2\right)$, so we must have $p-mf(m)=p-m^2$, i.e., $f(m)=m$.

Solution 3. Plugging $m=1$ we obtain $1+f(n)⩽f(1)+n$, so $f(n)⩽n+c$ for the constant $c=f(1)-1$. Assume that $f(n)\ne n$ for some fixed $n$. When $m$ is large enough (e.g. $m⩾\max (n,c+1)$ ) we have $$mf(m)+n⩽m(m+c)+n⩽2m^2<2\left(m^2+f(n)\right),$$ so we must have $mf(m)+n=m^2+f(n)$. This implies that $$0\ne f(n)-n=m(f(m)-m),$$ which is impossible for $m>|f(n)-n|$. It follows that $f$ is the identity function.