Maths Olympiad Prep

Library / /24 of 92

Algebra Difficulty 6.0 National olympiad Prove it Iran

Let f:R0R0f: \mathbb{R}^{\ge 0} \to \mathbb{R}^{\ge 0} be a function such that for all a,bR0a, b \in \mathbb{R}^{\ge 0}:
i) f(a)=0a=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,bR0a,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 kNk \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 2k1<n2k2^{k-1} < n \le 2^k:
f(a1++an)=f(a1++an+0+0++02kn)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++1n)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)aibni)2(n+1)max0in{f((ni)aibni)}2(n+1)i=0n(ni)f(ai)f(bni)4(n+1)f(1)i=0n(ni)f(a)if(b)ni=4(n+1)f(1)(f(a)+f(b))nf(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)n1\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,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.