# Intro

This is from IMO 1977, the only reason why I can solve it.

# Find

$f: \mathbb{Z^+} \rightarrow \mathbb{Z^+}$ such that $f(f(n)) < f(n+1) \forall n \in \mathbb{Z^+}$.

# Solution

Let $n_i \ \ (i \in \mathbb{Z^+})$ be a positive integer such that

Notice that $n_i$ can have multiple values since $D_i$ does not necessarily have a single mimimum (which we are going to prove against, but hold on).

Since $f(n_1) > f(f(n_1-1))$, either $n_1 - 1 \notin \mathbb{Z^+}$ or $f(n_1-1) \notin D_1$. The second one cannot hold by definition of $f$, so $n_1 - 1 \notin \mathbb{Z^+}$. Since $n_1 \in \mathbb{Z^+}$, $n_1 = 1$.

This means function $f$ achieves its minimum on $D_1$ at a single point $n_1=1$.

Move on to $n_2$. Similarly the case is either $n_2-1\notin\mathbb{Z^+}$ or $f(n_2-1)\notin D_2$. This time the first case cannot be satisfied, so $f(n_2-1)\notin D_2$ $(*)$.

If $n_2 > 2$, it follows that $n_2-1>n_1$. From the fact that $f$ has a single minimum at $n_1$, we conclude $f(n_2-1) > f(n_1)\geq 1$. This implies $f(n_2-1)\in D_2$, directly contradict with $(*)$. So $n_2 = 2$.

From this point, induction in a similar fashion gives $n_i=i$. From $D_1 \subseteq D_2 \subseteq D_3 \subseteq …$, we know $f(1)<f(2)<f(3)<…$.

Two things follow:

1. $f(n)\geq n \ \forall n$
2. $f$ strictly increases

From 2. and the what gives in the problem statement we have $f(n)< n+1 \ \forall n\in\mathbb{Z^+}$.

This and 1. give