48th International Mathematical Olympiad Vietnam 2007 Shortlisted Problems with Solutions

Suppose that a function $f:\mathbb{N}\to \mathbb{N}$ satisfies (1). For arbitrary positive integers $m>n$, by (1) we have $$f(m)=f(n+(m-n))\ge f(n)+f(f(m-n))-1\ge f(n),$$ so $f$ is nondecreasing.

Function $f\equiv 1$ is an obvious solution. To find other solutions, assume that $f\not\equiv 1$ and take the smallest $a\in \mathbb{N}$ such that $f(a)>1$. Then $f(b)\ge f(a)>1$ for all integer $b\ge a$.

Suppose that $f(n)>n$ for some $n\in \mathbb{N}$. Then we have $$f(f(n))=f((f(n)-n)+n)\ge f(f(n)-n)+f(f(n))-1$$ so $f(f(n)-n)\le 1$ and hence $f(n)-n<a$. Then there exists a maximal value of the expression $f(n)-n$; denote this value by $c$, and let $f(k)-k=c\ge 1$. Applying the monotonicity together with (1), we get $$\begin{array}{rl}2k+c\ge f(2k)=f(k+k)& \ge f(k)+f(f(k))-1\\ & \ge f(k)+f(k)-1=2(k+c)-1=2k+(2c-1),\end{array}$$ hence $c\le 1$ and $f(n)\le n+1$ for all $n\in \mathbb{N}$. In particular, $f(2007)\le 2008$.

Now we present a family of examples showing that all values from 1 to 2008 can be realized. Let $$f_j(n)=\max \{1,n+j-2007\}\text{ for }j=1,2,\dots ,2007;f_{2008}(n)=\{\begin{array}{ll}n,& 2007\nmid n,\\ n+1,& 2007\mid n.\end{array}$$ We show that these functions satisfy the condition (1) and clearly $f_j(2007)=j$.

To check the condition (1) for the function $f_j(j\le 2007)$, note first that $f_j$ is nondecreasing and $f_j(n)\le n$, hence $f_j\left(f_j(n)\right)\le f_j(n)\le n$ for all $n\in \mathbb{N}$. Now, if $f_j(m)=1$, then the inequality (1) is clear since $f_j(m+n)\ge f_j(n)\ge f_j\left(f_j(n)\right)=f_j(m)+f_j\left(f_j(n)\right)-1$. Otherwise, $$f_j(m)+f_j\left(f_j(n)\right)-1\le (m+j-2007)+n=(m+n)+j-2007=f_j(m+n).$$ In the case $j=2008$, clearly $n+1\ge f_{2008}(n)\ge n$ for all $n\in \mathbb{N}$; moreover, $n+1\ge f_{2008}\left(f_{2008}(n)\right)$ as well. Actually, the latter is trivial if $f_{2008}(n)=n$; otherwise, $f_{2008}(n)=n+1$, which implies $2007\nmid n+1$ and hence $n+1=f_{2008}(n+1)=f_{2008}\left(f_{2008}(n)\right)$.

So, if $2007\mid m+n$, then $$f_{2008}(m+n)=m+n+1=(m+1)+(n+1)-1\ge f_{2008}(m)+f_{2008}\left(f_{2008}(n)\right)-1.$$ Otherwise, $2007\nmid m+n$, hence $2007\nmid m$ or $2007\nmid n$. In the former case we have $f_{2008}(m)=m$, while in the latter one $f_{2008}\left(f_{2008}(n)\right)=f_{2008}(n)=n$, providing $$f_{2008}(m)+f_{2008}\left(f_{2008}(n)\right)-1\le (m+n+1)-1=f_{2008}(m+n)\text{.}$$