Saudi Arabian Mathematical Competitions

It is clear that $f(n) \geq 1$ for all $n \geq 1$. Assume that $f(n) \geq m$ for all $n \geq m$, for some $m \geq 1$. Let $n \geq m+1$. Because $n-1 \geq m$, we have $f(n-1) \geq m$ and therefore $f(f(n-1)) \geq m$. We deduce that $f(n) > \frac{f(n-1) + f(f(n-1))}{2} \geq m$. Hence, $f(n) \geq m+1$. In particular, $f(n) \geq n$ for all $n \in \mathbb{N}$.

Assume there exists $m$ for which $f(m) \geq m+2$. Then $f(f(m)) \geq f(m+2) \geq m+2$, and $f(m+1) > \frac{f(m) + f(f(m))}{2} \geq m+2$. This gives $f(m+1) \geq (m+1)+2$. It follows by induction that $f(n) \geq n+2$ for all $n \geq m$. Therefore, for all $n \geq m$, $f(n+1) - f(n) > f(f(n)) - f(n+1) \geq f(n+2) - f(n+1)$, which means that the sequence $f(n+1) - f(n)$ becomes decreasing from $m$ and this contradicts the fact $f(n) \geq n$ for all $n \in \mathbb{N}$. We deduce that
$$n \leq f(n) \leq n+1 \text{ for all } n \in \mathbb{N}$$
It is clear that the identity function is a solution. Assume that there exists $m \in \mathbb{N}$ such that $f(m) = m+1$. We have $m+2 \geq f(m+1) > f(m) + f(f(m)) - f(m+1) = m+1$. This proves that $f(m+1) = (m+1)+1$ and by induction $f(n) = n+1$, for all $n \geq m$. After checking, we conclude that the solutions are the identity function, $f(n) = n+1$ for all $n \in \mathbb{N}$, and all the functions which can be written
$$f(n) = \begin{cases} n & \text{ if } n < m \\ n+1 & \text{ if } n \geq m \end{cases}$$
for some $m > 1$.