alt text     alt text     alt text     alt text     alt text



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


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


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


alt text     alt text     alt text     alt text     alt text