Maths Olympiad Prep

Library / /128 of 155

Algebra Difficulty 6.9 National olympiad Prove it Saudi Arabia

Find all functions f:Z+Z+f: \mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+} such that
n3n2f(n)(f(f(n)))2n3+n2 n^{3}-n^{2} \leq f(n) \cdot (f(f(n)))^{2} \leq n^{3}+n^{2}
for every nn is positive integers.

Solution

Firstly, we prove that ff is injective. Let two natural numbers a,ba, b such that a+1ba+1 \leq b and f(a)=f(b)f(a)=f(b). By the given condition, we have
f(a)[f(f(a))]2a3+a2<a3+2a2+a=(a+1)3(a+1)2. f(a)[f(f(a))]^{2} \leq a^{3}+a^{2}<a^{3}+2a^{2}+a=(a+1)^{3}-(a+1)^{2}.
Since a,bZ+a, b \in \mathbb{Z}^{+} and a+1ba+1 \leq b, we have
(a+1)3(a+1)2b3b2f(b)[f(f(b))]2. (a+1)^{3}-(a+1)^{2} \leq b^{3}-b^{2} \leq f(b)[f(f(b))]^{2}.
Thus f(a)[f(f(a))]2<f(b)[f(f(b))]2f(a)[f(f(a))]^{2}<f(b)[f(f(b))]^{2}, a contradiction. This implies ff is injective.

In given condition, let n=1n=1, we have
0f(1)[f(f(1))]22. 0 \leq f(1)[f(f(1))]^{2} \leq 2.
Since f:Z+Z+f: \mathbb{Z}^{+} \longrightarrow \mathbb{Z}^{+}, we have two cases
- f(1)=1f(1)=1.
- f(1)=2f(1)=2 and f(2)=1f(2)=1.

We shall prove that if {f(1),,f(k)}={1,,k}\{f(1), \ldots, f(k)\}=\{1, \ldots, k\} then either f(k+1)=k+1f(k+1)=k+1 or f(k+1)=k+2,f(k+2)=k+2f(k+1)=k+2, f(k+2)=k+2. Indeed,
Since ff is injective, we have f(k+1)k+1f(k+1) \geq k+1. If f(k+1)=k+1f(k+1)=k+1, we have
{f(1),,f(k+1)}={1,,k+1}. \{f(1), \ldots, f(k+1)\}=\{1, \ldots, k+1\}.
Otherwise, if f(k+1)k+2f(k+1) \geq k+2, we have [f(f(k+1))]2(k+1)2[f(f(k+1))]^{2} \geq (k+1)^{2}. In given condition, let n=k+1n=k+1, we have
(k+1)3+(k+1)2f(k+1)[f(f(k+1))]2(k+2)(k+1)2. (k+1)^{3}+(k+1)^{2} \geq f(k+1)[f(f(k+1))]^{2} \geq (k+2)(k+1)^{2}.
Since (k+1)3+(k+1)2=(k+2)(k+1)2(k+1)^{3}+(k+1)^{2}=(k+2)(k+1)^{2}, we deduce that f(k+1)=k+2f(k+1)=k+2 and f(k+2)=k+1f(k+2)=k+1. Thus {f(1),,f(k+2)}={1,,k+2}\{f(1), \ldots, f(k+2)\}=\{1, \ldots, k+2\}.

Now we can check both cases satisfy the conditions
(k+2)3(k+2)2f(k+2)f(f(k+2))2(k+2)3+(k+2)2(k+2)2(k+1)(k+1)(k+2)2(k+2)2(k+3). \begin{aligned} & (k+2)^{3}-(k+2)^{2} \leq f(k+2) f(f(k+2))^{2} \leq (k+2)^{3}+(k+2)^{2} \\ & \Leftrightarrow (k+2)^{2}(k+1) \leq (k+1)(k+2)^{2} \leq (k+2)^{2}(k+3). \end{aligned}
Therefore, the solutions of this problem are the functions have following properties
- There are some disjoint pairs (k,k+1)(k, k+1) with f(k)=k+1f(k)=k+1 and f(k+1)=f(k)f(k+1)=f(k).
- For other positive integer aa, then f(a)=af(a)=a.

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 and solution reproduced as published; topic and difficulty added by this site.