Maths Olympiad Prep

Library / /5 of 9

, 2018

Algebra Difficulty 8.3 Shortlist Prove it Saudi Arabia

Find all functions f:Z+Z+f: \mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+} satisfying f(1)=2f(1)=2, f(2)4f(2) \neq 4, and
max{f(m)+f(n),m+n}min{2m+2n,f(m+n)+1} \max \{f(m)+f(n), m+n\} \mid \min \{2m+2n, f(m+n)+1\}
for all m,nZ+m, n \in \mathbb{Z}^{+}.

Solution

In given condition, substitute m=nm=n, we have
max{2f(n),2n}min{4n,f(2n)+1}, \max \{2 f(n), 2 n\} \mid \min \{4 n, f(2 n)+1\},
thus 4n2f(n)4 n \geq 2 f(n) or f(n)2nf(n) \leq 2 n.
Continue substitute m=1m=1, we have
max{2+f(n),1+n}min{2+2n,f(1+n)+1}() \max \{2+f(n), 1+n\} \mid \min \{2+2 n, f(1+n)+1\} \quad (*)
Thus f(n+1)+1f(n)+2f(n+1)+1 \geq f(n)+2 or f(n+1)f(n)+1f(n+1) \geq f(n)+1. Since f(1)=2f(1)=2, we have f(n)n+1,nZ+f(n) \geq n+1, \forall n \in \mathbb{Z}^{+}.
From these, we can conclude that f(2){3;4}f(2) \in \{3 ; 4\}. But we have f(2)4f(2) \neq 4 then f(2)=3f(2)=3. We shall prove by induction that f(n)=n+1,n2f(n)=n+1, \forall n \geq 2.
The conclusion is true for n=1,2n=1,2. Suppose that f(n)=n+1f(n)=n+1 for some n2n \geq 2.
Back to (*), note that max{2+f(n),1+n}=f(n)+2=n+3\max \{2+f(n), 1+n\}=f(n)+2=n+3 and 2n+2n+3(1;2)\frac{2 n+2}{n+3} \in (1; 2) which implies that n+32n+2n+3 \nmid 2 n+2. Hence
min{2+2n,f(1+n)+1}=f(n+1)+1 \min \{2+2 n, f(1+n)+1\}=f(n+1)+1
Since n+2f(n+1)2n+2n+2 \leq f(n+1) \leq 2 n+2, we must have f(n+1)+1n+3=1f(n+1)=n+2\frac{f(n+1)+1}{n+3}=1 \Leftrightarrow f(n+1)=n+2. By induction hypothesis, we get f(n)=n+1f(n)=n+1.
Check condition, for all m,nZ+m, n \in \mathbb{Z}^{+} then
min{2m+2n,f(m+n)+1}=min{2m+2n,m+n+2}=m+n+2 and max{f(m)+f(n),m+n}=max{m+1+n+1,m+n}=m+n+2 \begin{gathered} \min \{2 m+2 n, f(m+n)+1\}=\min \{2 m+2 n, m+n+2\}=m+n+2 \text{ and } \\ \max \{f(m)+f(n), m+n\}=\max \{m+1+n+1, m+n\}=m+n+2 \end{gathered}
Hence, the function f(n)=n+1f(n)=n+1 satisfies the given condition.

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.