Maths Olympiad Prep

Library / /3 of 25

Algebra Difficulty 5.2 AIME, harder Prove it North Macedonia

Find all injection functions f:NNf: \mathbb{N} \rightarrow \mathbb{N} such that
f(f(n))n+f(n)2,nN. f(f(n)) \leq \frac{n+f(n)}{2}, \forall n \in \mathbb{N}.

Solution

Let ff be the solution. Then
f(f(n))max{n,f(n)},nN.() f(f(n)) \leq \max\{n, f(n)\}, \forall n \in \mathbb{N}. \quad (*)
Let fk(a)=f(f(...f(a)))kf^k(a) = \underbrace{f(f(...f(a)))}_{k}. Now there is aa such that a>f(a)a > f(a). Then f2(a)<af^2(a) < a; by induction to kk it's easy to prove that
fk(a)<a,k>0.(1) f^k(a) < a, \forall k > 0. \quad (1)
Because the set {1,2,...,a1}\{1, 2, ..., a-1\} is finite, there is i,ji, j such that 0<i<j0 < i < j and
f(a)=f(a)=f(fji(a)). f'(a) = f'(a) = f'(f^{j-i}(a)).
The function ff is injection so fji(a)=af^{j-i}(a) = a, which is contradiction to (1). Then
af(a),a>0(2) a \leq f(a), \forall a > 0 \quad (2)
and f(a)f(f(a)),aNf(a) \leq f(f(a)), \forall a \in \mathbb{N}.
On another side, from (*) and (2) we have f(f(a))max{a,f(a)}=f(a)f(f(a)) \leq \max\{a, f(a)\} = f(a) i.e. f(f(a))=f(a)f(f(a)) = f(a).
Finally f(a)=a,aNf(a) = a, \forall a \in \mathbb{N}. So f(n)=n,nNf(n) = n, \forall n \in \mathbb{N}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.