Let $f(x)=(x + a)(x + b)$ where $a,b>0$. For any reals $x_1,x_2,\ldots ,x_n\geqslant 0$ satisfying $x_1+x_2+\ldots +x_n =1$, find the maximum of $F=\sum\limits_{1 \leqslant i < j \leqslant n} {\min \left\{ {f({x_i}),f({x_j})} \right\}} $.
Problem
Source: 2012 China Mathematical Olympaid P4
Tags: inequalities, inequalities proposed
13.01.2012 16:32
Posted here yesterday.
16.01.2012 11:48
Lemma: $n \geqslant 2$ is a integer, $T > 0$ is a real number, then for any ${x_1},{x_2},...,{x_n} \geqslant 0$ satisfy ${x_1} + {x_2} + ... + {x_n} = T$, ${F_n}({x_1},{x_2},...,{x_n}) = \sum\limits_{1 \leqslant i < j \leqslant n} {\min \left\{ {f({x_i}),f({x_j})} \right\}} $ is maximum if and only if ${x_1} = {x_2} = ... = {x_n}$. Proof: Suppose ${x_1} \leqslant {x_2} \leqslant ... \leqslant {x_n}$, then $f({x_1}) \leqslant f({x_2}) \leqslant ... \leqslant f({x_n})$, so ${F_n}({x_1},{x_2},...,{x_n}) = \sum\limits_{i = 1}^{n - 1} {(n - i)f({x_i})} $. IF $n = 2$, $F({x_1},{x_2}) = f({x_1})$, $0 \leqslant {x_1} \leqslant \frac{T}{2}$. so ${F_2}({x_1},{x_2}) = f({x_1}) \leqslant f\left( {\frac{T}{2}} \right)$, ${F_2}({x_1},{x_2})$ is maximum if and only if ${x_1} = \frac{T}{2} = {x_2}$. If the lemma is true for some $k \geqslant 2$, now suppose ${x_1} + {x_2} + ... + {x_{k+1}} = T$. Because ${F_{k + 1}}({x_1},{x_2},...,{x_{k + 1}}) = kf({x_1}) + {F_k}({x_2},{x_3},...,{x_{k + 1}})$, hence if ${F_{k + 1}}({x_1},{x_2},...,{x_{k + 1}})$ is maximum , then ${F_k}({x_2},{x_3},...,{x_{k + 1}})$ is maximum under ${x_2} + {x_3} + ... + {x_{k + 1}} = T - {x_1}$, so ${x_2} = {x_3} = ... = {x_{k + 1}} = \frac{{T - {x_1}}}{k}$, ${F_{k + 1}}({x_1},{x_2},...,{x_{k + 1}}) = kf({x_1}) + \frac{{k(k - 1)}}{2}f\left( {\frac{{T - {x_1}}}{k}} \right) = g({x_1})$,${x_1} \in \left[ {0,\frac{T}{{k + 1}}} \right]$, $g({x_1}) = \left[ {k + \frac{{k - 1}}{{2k}}} \right]x_1^2 + Ax + B$. Because $k + \frac{{k - 1}}{{2k}} > 0$, so the maximum of $g({x_1})$ is $max\left\{ {g(0),g\left( {\frac{T}{{k + 1}}} \right)} \right\} = g\left( {\frac{T}{{k + 1}}} \right)$, so ${x_1} = {x_2} = ... = {x_{k + 1}} = \frac{T}{{k + 1}}$. QED. By the lemma the maximum of $F$ is $\frac{{n(n - 1)}}{2}f\left( {\frac{1}{n}} \right) = \frac{{(n - 1)}}{{2n}}\left( {na + 1} \right)\left( {nb + 1} \right)$.
03.02.2012 14:48
this is my solution in CMO. $ F=\sum\limits_{1\leqslant i < j\leqslant n}{\min\left\{{f({x_{i}}),f({x_{j}})}\right\}} \leqslant \sum\limits_{1\leqslant i < j\leqslant n}{\sqrt{f({x_{i})f({x_{j})}}}=((\sum\limits_{i = 1}^{n}\sqrt{f({x_{i}})})^{2}-\sum\limits_{i = 1}^{n}f(x_{i}))/2}$ since $g(x)=\sqrt{f(x)}$is concave while f(x) is convex on $R^{+}$ Jensen's inequality tells us that F obtains its maximum if and only if x1=x2=...=xn and we're done.
04.02.2012 08:02
gcshudder wrote: since $g(x)=\sqrt{f(x)}$is concave while f(x) is convex on $R^{+}$ $g''(x)=\frac{2f''(x)f(x)-\left(f'(x)\right)^2}{4\sqrt{\left(f(x)\right)^3}}$. Why $2f''(x)f(x)-\left(f'(x)\right)^2\leq0$ for $f''(x)\geq0$? In our case indeed $\left(\sqrt{(x+a)(x+b)}\right)''=-\frac{(a-b)^2}{4\sqrt{(x+a)^3(x+b)^3}}\leq0$.
04.02.2012 14:32
But I still don't understand that proof.. Using Jensen we get: $ \frac{1}{2}\left[ \left( \sum_{i=1}^{n} \sqrt{f(x_i)} \right)^2 - \sum_{i=1}^{n} f(x_i) \right] \le \frac{1}{2}\left[ n\cdot \sum_{i=1}^{n} f(x_i) - \sum_{i=1}^{n} f(x_i) \right] \\ = \frac{n-1}{2} \cdot \sum_{i=1}^{n} f(x_i)$ And what now? $\sum_{i=1}^{n} f(x_i)$ reaches maximum when $x_1=1, \; x_2=x_3=...=x_n=0$ because $f(x_i)$ is convex. Can you please post full proof because I'm not sure if it's correct...
10.02.2012 10:47
arqady wrote: gcshudder wrote: since $g(x)=\sqrt{f(x)}$is concave while f(x) is convex on $R^{+}$ $g''(x)=\frac{2f''(x)f(x)-\left(f'(x)\right)^2}{4\sqrt{\left(f(x)\right)^3}}$. Why $2f''(x)f(x)-\left(f'(x)\right)^2\leq0$ for $f''(x)\geq0$? In our case indeed $\left(\sqrt{(x+a)(x+b)}\right)''=-\frac{(a-b)^2}{4\sqrt{(x+a)^3(x+b)^3}}\leq0$. I'm sorry but I used the wrong word. maybe $g''\le 0$ and $ f''>0 $(which can be easily confirmed) is better. I think this solution is a nice one but it cannot be generalized.
10.02.2012 11:02
MathUniverse wrote: But I still don't understand that proof.. Using Jensen we get: $ \frac{1}{2}\left[ \left( \sum_{i=1}^{n} \sqrt{f(x_i)} \right)^2 - \sum_{i=1}^{n} f(x_i) \right] \le \frac{1}{2}\left[ n\cdot \sum_{i=1}^{n} f(x_i) - \sum_{i=1}^{n} f(x_i) \right] \\ = \frac{n-1}{2} \cdot \sum_{i=1}^{n} f(x_i)$ And what now? $\sum_{i=1}^{n} f(x_i)$ reaches maximum when $x_1=1, \; x_2=x_3=...=x_n=0$ because $f(x_i)$ is convex. Can you please post full proof because I'm not sure if it's correct... $ \sum_{i=1}^{n}g(x_{i})\le n\cdot g(\frac{\sum_{i=1}^{n}x_{i}}{n})=ng(\frac{1}{n})$ $ \sum_{i=1}^{n}f(x_{i})\ge n\cdot f(\frac{\sum_{i=1}^{n}x_{i}}{n})=nf(\frac{1}{n})$ hence $ \frac{1}{2}\left[ \left( \sum_{i=1}^{n} g(x_i) \right)^2 - \sum_{i=1}^{n} f(x_i) \right] \le\frac{1}{2}\left[ (ng(\frac{1}{n}))^{2}-nf(\frac{1}{n})\right]=\frac{n^{2}-n}{2}\cdot f(\frac{1}{n})$