1. Find all injections $f: \mathbb{N} \rightarrow \mathbb{N}$ for which

$$
f(f(n)) \leq \frac{n+f(n)}{2}, \forall n \in \mathbb{N}
$$
Solution. Let $f$ be a solution. Note that

$$
f(f(n)) \leq \max \{n, f(n)\}, \forall n \in \mathbb{N}
$$

Let

$$
f^{k}(a)=\underbrace{f(f(\ldots f(a)) \ldots)}_{k}
$$

Assume there exists $a$ such that $a > f(a)$. Then

$$
f^{2}(a) \stackrel{(*)}{\leq} f(a) < a
$$

Since the set $\{1,2, \ldots, a-1\}$ is finite, it follows that there exist $i, j$ such that $0 < i < j$ and

$$
f^{i}(a) = f^{j}(a)
$$

Then

$$
f(a) \leq f(f(a)), \forall a \in \mathbb{N}
$$

On the other hand, due to (*) and (2) we have

$$
f(f(a)) \leq \max \{a, f(a)\} = f(a)
$$

i.e.

$$
f(f(a)) = f(a)
$$

and finally, due to the injectivity of $f$, we get $f(a) = a, \forall a \in \mathbb{N}$. Therefore,

$$
f(n) = n, \forall n \in \mathbb{N}
$$