Maths Olympiad Prep

Library / Iranian Mathematical Olympiad /68 of 270

Iranian Mathematical Olympiad

Algebra Difficulty 6.0 National Olympiad Prove it Iran

Let f:R≥0→R≥0f: \mathbb{R}^{\ge 0} \to \mathbb{R}^{\ge 0} be a function such that for all a,b∈R≥0a, b \in \mathbb{R}^{\ge 0}:
i) f(a)=0⇔a=0f(a) = 0 \Leftrightarrow a = 0.
ii) f(ab)=f(a)f(b)f(ab) = f(a)f(b).
iii) f(a+b)≤2max⁡{f(a),f(b)}f(a + b) \le 2 \max\{f(a), f(b)\}.

Prove that for every a,b∈R≥0a,b \in \mathbb{R}^{\ge 0}, f(a+b)≤f(a)+f(b)f(a+b) \le f(a) + f(b).

Solution

We claim that for every k∈Nk \in \mathbb{N} and real numbers a1,a2,…,a2ka_1, a_2, \dots, a_{2^k}:
f(a1+a2+⋯+a2k)≤2kmax⁡{f(a1),f(a2),…,f(a2k)} f(a_1 + a_2 + \cdots + a_{2^k}) \le 2^k \max\{f(a_1), f(a_2), \dots, f(a_{2^k})\}
Proof is done by induction on kk. Basis is obviously the condition (iii). Suppose the claim is true for kk. For k+1k+1 we have:
f(a1+a2+⋯+a2k+1)=f((a1+a2+⋯+a2k)+(a2k+1+⋯+a2k+1))≤2max⁡{f(a1+a2+⋯+a2k),f(a2k+1+⋯+a2k+1)}≤2max⁡{2kmax⁡{f(a1),f(a2),…,f(a2k)},2kmax⁡{f(a2k+1),…,f(a2k+1)}}≤2k+1max⁡{f(a1),f(a2),…,f(a2k+1)} \begin{align*} f(a_1 + a_2 + \cdots + a_{2^{k+1}}) &= f((a_1 + a_2 + \cdots + a_{2^k}) + (a_{2^k+1} + \cdots + a_{2^{k+1}})) \\ &\le 2 \max\{f(a_1 + a_2 + \cdots + a_{2^k}), f(a_{2^k+1} + \cdots + a_{2^{k+1}})\} \\ &\le 2 \max\{2^k \max\{f(a_1), f(a_2), \dots, f(a_{2^k})\}, 2^k \max\{f(a_{2^k+1}), \dots, f(a_{2^{k+1}})\}\} \\ &\le 2^{k+1} \max\{f(a_1), f(a_2), \dots, f(a_{2^{k+1}})\} \end{align*}
Now suppose that 2k−1<n≤2k2^{k-1} < n \le 2^k:
f(a1+⋯+an)=f(a1+⋯+an+0+0+⋯+0⏟2k−n)≤2kmax⁡{f(a1),…,f(an),f(0),…,f(0)}=2kmax⁡{f(a1),…,f(an)}≤2nmax⁡{f(a1),…,f(an)} \begin{align*} f(a_1 + \cdots + a_n) &= f(a_1 + \cdots + a_n + \underbrace{0 + 0 + \cdots + 0}_{2^k - n}) \\ &\le 2^k \max\{f(a_1), \dots, f(a_n), f(0), \dots, f(0)\} \\ &= 2^k \max\{f(a_1), \dots, f(a_n)\} \le 2n \max\{f(a_1), \dots, f(a_n)\} \end{align*}
If we put a1=a2=⋯=an=1a_1 = a_2 = \cdots = a_n = 1 then f(n)=f(1+1+⋯+1⏟n)≤2nf(1)f(n) = f(\underbrace{1+1+\cdots+1}_{n}) \le 2nf(1). Therefore
(f(a+b))n=f((a+b)n)=f(∑i=0n(ni)aibn−i)≤2(n+1)max⁡0≤i≤n{f((ni)aibn−i)}≤2(n+1)∑i=0n(ni)f(ai)f(bn−i)≤4(n+1)f(1)∑i=0n(ni)f(a)if(b)n−i=4(n+1)f(1)(f(a)+f(b))n⇒f(a+b)≤4(n+1)f(1)(f(a)+f(b))n \begin{align*} (f(a+b))^n &= f((a+b)^n) = f\left(\sum_{i=0}^{n} \binom{n}{i} a^i b^{n-i}\right) \le 2(n+1) \max_{0 \le i \le n} \{f\left(\binom{n}{i} a^i b^{n-i}\right)\} \\ &\le 2(n+1) \sum_{i=0}^{n} \binom{n}{i} f(a^i) f(b^{n-i}) \le 4(n+1)f(1) \sum_{i=0}^{n} \binom{n}{i} f(a)^i f(b)^{n-i} \\ &= 4(n+1)f(1)(f(a)+f(b))^n \Rightarrow f(a+b) \le \sqrt[n]{4(n+1)f(1)(f(a)+f(b))} \end{align*}
If nn tends to infinity, we have 4(n+1)f(1)n→1\sqrt[n]{4(n+1)f(1)} \to 1 and this implies the desired result. □\square

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

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