Kanada 2015

The only such function is $f(n)=n$. Assume that $f$ satisfies the given condition. It will be shown by induction that $f(n)=n$ for all $n\in \mathbb{N}$. Substituting $n=1$ yields that $0<f(1)f(f(1))<2$ which implies the base case $f(1)=1$. Now assume that $f(k)=k$ for all $k<n$ and assume for contradiction that $f(n)\ne n$. On the one hand, if $f(n)\le n-1$ then $f(f(n))=f(n)$ and $f(n)f(f(n))=f(n{)}^2\le (n-1{)}^2$ which is a contradiction. On the other hand, if $f(n)\ge n+1$ then there are several ways to proceed.

Method 1: Assume $f(n)=M\ge n+1$. Then $(n+1)f(M)\le f(n)f(f(n))<n^2+n$. Therefore $f(M)<n$, and hence $f(f(M))=f(M)$ and $f(M)f(f(M))=f(M{)}^2<n^2\le (M-1{)}^2$, which is a contradiction. This completes the induction. $\square$

Method 2: First note that if $|a-b|>1$, then the intervals $((a-1{)}^2,a^2+a)$ and $((b-1{)}^2,b^2+b)$ are disjoint which implies that $f(a)$ and $f(b)$ cannot be equal. Assuming $f(n)\ge n+1$, it follows that $f(f(n))<\frac{n^2+n}{f(n)}\le n$. This implies that for some $a\le n-1$, $f(a)=f(f(n))$ which is a contradiction since $|f(n)-a|\ge n+1-a\ge 2$. This completes the induction. $\square$

Method 3: Assuming $f(n)\ge n+1$, it follows that $f(f(n))<\frac{n^2+n}{f(n)}\le n$ and $f(f(f(n)))=f(f(n))$. This implies that $(f(n)-1{)}^2<f(f(n))f(f(f(n)))=f(f(n){)}^2<f(n{)}^2+f(n)$ and therefore that $f(f(n))=f(n)$ since $f(n{)}^2$ is the unique square satisfying this constraint. This implies that $f(n)f(f(n))=f(n{)}^2\ge (n+1{)}^2$ which is a contradiction, completing the induction. $\square$