Olympiad Maths Prep

Track / Stage 7 / 255 of 300 #1655 of 2000

Problem 1655

National olympiad second round; IMO P1/P4
Algebra Difficulty 7.7 Prove it Vietnamese Mathematical Competitions · Vietnam

Let be given an integer n≥4n \ge 4 and x1,x2,x3,…,xnx_1, x_2, x_3, \dots, x_n be nonnegative real numbers.
a) Prove that we have inequality
(∑i=1nxi)2≥min⁡{n3,83}∑i=1nxi(xi+1+xi+2+xi+3) \left(\sum_{i=1}^{n} x_i\right)^2 \ge \min\left\{\frac{n}{3}, \frac{8}{3}\right\} \sum_{i=1}^{n} x_i (x_{i+1} + x_{i+2} + x_{i+3})
where xn+1=x1x_{n+1} = x_1, xn+2=x2x_{n+2} = x_2, xn+3=x3x_{n+3} = x_3.
b) When does the equality hold?

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Firstly, we will prove inequality (*) for n=4,5,6,7,8n = 4, 5, 6, 7, 8.

- For n=4n = 4, we need to prove (∑i=14xi)2≥43∑i=14xi(xi+1+xi+2+xi+3)\left(\sum_{i=1}^{4} x_i\right)^2 \ge \frac{4}{3} \sum_{i=1}^{4} x_i (x_{i+1} + x_{i+2} + x_{i+3}).
We have ∑i=14xi(xi+1+xi+2+xi+3)=(∑i=14xi)2−4∑i=14xi2\sum_{i=1}^{4} x_i (x_{i+1} + x_{i+2} + x_{i+3}) = \left(\sum_{i=1}^{4} x_i\right)^2 - 4 \sum_{i=1}^{4} x_i^2 so we need to prove that
3(∑i=14xi)2≥4(∑i=14xi)2−4∑i=14xi2⇔4∑i=14xi2≥(∑i=14xi)2. 3\left(\sum_{i=1}^{4} x_i\right)^2 \ge 4\left(\sum_{i=1}^{4} x_i\right)^2 - 4\sum_{i=1}^{4} x_i^2 \Leftrightarrow 4\sum_{i=1}^{4} x_i^2 \ge \left(\sum_{i=1}^{4} x_i\right)^2.
The last inequality is true by Cauchy-Schwarz inequality.
So the case n=4n = 4 is proved.
The equality occurs if and only if x1=x2=x3=x4x_1 = x_2 = x_3 = x_4.

- For n=5n = 5, we should have (∑i=15xi)2≥53∑i=15xi(xi+1+xi+2+xi+3)\left(\sum_{i=1}^{5} x_i\right)^2 \ge \frac{5}{3} \sum_{i=1}^{5} x_i (x_{i+1} + x_{i+2} + x_{i+3}).
We have ∑i=15xi(xi+1+xi+2+xi+3)=(∑i=15xi)2−∑i=15(xi2+xixi−1)\sum_{i=1}^{5} x_i (x_{i+1} + x_{i+2} + x_{i+3}) = \left(\sum_{i=1}^{5} x_i\right)^2 - \sum_{i=1}^{5} (x_i^2 + x_i x_{i-1}) where x0=x5x_0 = x_5 so we need to prove that
3(∑i=15xi)2≥5(∑i=15xi)2−5∑i=15(xi2+xixi−1)⇔5∑i=15(xi2+xixi−1)≥2(∑i=15xi)2⇔5∑i=15(xi+xi−12)2≥(∑i=15xi)2⇔5∑i=15(xi+xi−12)2≥(∑i=15xi+xi−12)2. 3\left(\sum_{i=1}^{5} x_i\right)^2 \ge 5\left(\sum_{i=1}^{5} x_i\right)^2 - 5\sum_{i=1}^{5} (x_i^2 + x_i x_{i-1}) \Leftrightarrow 5\sum_{i=1}^{5} (x_i^2 + x_i x_{i-1}) \ge 2\left(\sum_{i=1}^{5} x_i\right)^2 \\ \Leftrightarrow 5\sum_{i=1}^{5} \left(\frac{x_i + x_{i-1}}{2}\right)^2 \ge \left(\sum_{i=1}^{5} x_i\right)^2 \Leftrightarrow 5\sum_{i=1}^{5} \left(\frac{x_i + x_{i-1}}{2}\right)^2 \ge \left(\sum_{i=1}^{5} \frac{x_i + x_{i-1}}{2}\right)^2.
The last inequality is true by Cauchy-Schwarz inequality.
The equality occurs if and only if x1=x2=x3=x4=x5x_1 = x_2 = x_3 = x_4 = x_5.

- For n=6n=6, we should have (∑i=16xi)2≥2∑i=16xi(xi+1+xi+2+xi+3)\left(\sum_{i=1}^{6} x_i\right)^2 \ge 2 \sum_{i=1}^{6} x_i (x_{i+1} + x_{i+2} + x_{i+3}).
We have ∑i=16xi(xi+1+xi+2+xi+3)=2(∑1≤i<j≤6xixj+x1x4+x2x5+x3x6)\sum_{i=1}^{6} x_i (x_{i+1} + x_{i+2} + x_{i+3}) = 2 \left( \sum_{1 \le i < j \le 6} x_i x_j + x_1 x_4 + x_2 x_5 + x_3 x_6 \right) so we need to
prove that
(∑i=16xi)2≥2(∑1≤i<j≤6xixj+x1x4+x2x5+x3x6)⇔(x1−x4)2+(x2−x5)2+(x3−x6)2≥0. \left(\sum_{i=1}^{6} x_i\right)^2 \ge 2 \left( \sum_{1 \le i < j \le 6} x_i x_j + x_1 x_4 + x_2 x_5 + x_3 x_6 \right) \Leftrightarrow (x_1 - x_4)^2 + (x_2 - x_5)^2 + (x_3 - x_6)^2 \ge 0.
The last inequality is true. The equality holds if and only if x1=x4,x2=x5,x3=x6x_1 = x_4, x_2 = x_5, x_3 = x_6.

- For n=7n=7, we need to prove that (∑i=17xi)2≥73∑i=17xi(xi+1+xi+2+xi+3)\left(\sum_{i=1}^{7} x_i\right)^2 \ge \frac{7}{3} \sum_{i=1}^{7} x_i (x_{i+1} + x_{i+2} + x_{i+3}).
We have
2∑i=17xi(xi+1+xi+2+xi+3)=∑i=17xi(xi+1+xi+2+xi+3+xi−1+xi−2+xi−3)=(∑i=17xi)2−∑i=17xi2 2 \sum_{i=1}^{7} x_i (x_{i+1} + x_{i+2} + x_{i+3}) = \sum_{i=1}^{7} x_i (x_{i+1} + x_{i+2} + x_{i+3} + x_{i-1} + x_{i-2} + x_{i-3}) = \left(\sum_{i=1}^{7} x_i\right)^2 - \sum_{i=1}^{7} x_i^2
So, we need to prove that (∑i=17xi)2≥76[(∑i=17xi)2−∑i=17xi2]⇔7∑i=17xi2≥(∑i=17xi)2\left(\sum_{i=1}^{7} x_i\right)^2 \ge \frac{7}{6} \left[ \left(\sum_{i=1}^{7} x_i\right)^2 - \sum_{i=1}^{7} x_i^2 \right] \Leftrightarrow 7 \sum_{i=1}^{7} x_i^2 \ge \left(\sum_{i=1}^{7} x_i\right)^2.
The last inequality is true by Cauchy-Schwarz inequality.
The equality occurs if and only if x1=x2=x3=x4=x5=x6=x7x_1 = x_2 = x_3 = x_4 = x_5 = x_6 = x_7.

- For n=8n=8, we should have (∑i=18xi)2≥83∑i=18xi(xi+1+xi+2+xi+3)\left(\sum_{i=1}^{8} x_i\right)^2 \ge \frac{8}{3} \sum_{i=1}^{8} x_i (x_{i+1} + x_{i+2} + x_{i+3}). We have
2∑i=18xi(xi+1+xi+2+xi+3)=∑i=18xi(xi+1+xi+2+xi+3+xi−1+xi−2+xi−3)=(∑i=18xi)2−∑i=18(xi2+xixi+4) 2 \sum_{i=1}^{8} x_i (x_{i+1} + x_{i+2} + x_{i+3}) = \sum_{i=1}^{8} x_i (x_{i+1} + x_{i+2} + x_{i+3} + x_{i-1} + x_{i-2} + x_{i-3}) = \left(\sum_{i=1}^{8} x_i\right)^2 - \sum_{i=1}^{8} (x_i^2 + x_i x_{i+4})
We need to prove that
3(∑i=18xi)2≥4(∑i=18xi)2−4∑i=18(xi2+xixi+4)⇔4∑i=18(xi2+xixi+4)≥(∑i=18xi)2⇔8∑i=18(xi+xi+42)2≥(∑i=18xi+xi+42)2 \begin{aligned} 3 \left(\sum_{i=1}^{8} x_i\right)^2 &\ge 4 \left(\sum_{i=1}^{8} x_i\right)^2 - 4 \sum_{i=1}^{8} (x_i^2 + x_i x_{i+4}) \\ &\Leftrightarrow 4 \sum_{i=1}^{8} (x_i^2 + x_i x_{i+4}) \ge \left(\sum_{i=1}^{8} x_i\right)^2 \\ &\Leftrightarrow 8 \sum_{i=1}^{8} \left(\frac{x_i + x_{i+4}}{2}\right)^2 \ge \left(\sum_{i=1}^{8} \frac{x_i + x_{i+4}}{2}\right)^2 \end{aligned}
The last inequality is true by Cauchy-Schwarz inequality. The equality occurs iff
x1+x5=x2+x6=x3+x7=x4+x8x_1 + x_5 = x_2 + x_6 = x_3 + x_7 = x_4 + x_8.

Next, for n≥8n \ge 8, we will prove that 3(∑i=1nxi)2≥8∑i=1nxi(xi+1+xi+2+xi+3)3\left(\sum_{i=1}^{n} x_i\right)^2 \ge 8\sum_{i=1}^{n} x_i (x_{i+1} + x_{i+2} + x_{i+3}) by induction.
- For n=8n=8 the statement is true.
- Assume that the statement is true for all nn-tuple (x1,x2,x3,…,xn)(x_1, x_2, x_3, \dots, x_n). Consider n+1n+1 nonnegative numbers (x1,x2,x3,…,xn,xn+1)(x_1, x_2, x_3, \dots, x_n, x_{n+1}) with xn+1=min⁡{x1,x2,x3,…,xn,xn+1}x_{n+1} = \min\{x_1, x_2, x_3, \dots, x_n, x_{n+1}\}.
Put Sn=∑i=1nxiS_n = \sum_{i=1}^{n} x_i, Pn=∑i=1nxi(xi+1+xi+2+xi+3)P_n = \sum_{i=1}^{n} x_i (x_{i+1} + x_{i+2} + x_{i+3}), we have to prove that Sn2≥83PnS_n^2 \ge \frac{8}{3}P_n for n≥8n \ge 8.
We have
3Sn+12=3(Sn+xn+1)2=3(Sn2+xn+12+2xn+1Sn) and3S_{n+1}^2 = 3(S_n + x_{n+1})^2 = 3(S_n^2 + x_{n+1}^2 + 2x_{n+1}S_n) \text{ and}
8Pn+1=8Pn+8[xn−2(xn+1−x1)+xn−1(xn+1−x2)+xn(xn+1−x3)+xn+1(x1+x2+x3)].8P_{n+1} = 8P_n + 8[x_{n-2}(x_{n+1}-x_1) + x_{n-1}(x_{n+1}-x_2) + x_n(x_{n+1}-x_3) + x_{n+1}(x_1+x_2+x_3)].
By the induction hypothesis then Sn2≥83PnS_n^2 \ge \frac{8}{3}P_n so, it is sufficient to prove that
3xn+12+6xn+1Sn≥8[xn−2(xn+1−x1)+xn−1(xn+1−x2)+xn(xn+1−x3)+xn+1(x1+x2+x3)] (**) 3x_{n+1}^2 + 6x_{n+1}S_n \ge 8[x_{n-2}(x_{n+1}-x_1) + x_{n-1}(x_{n+1}-x_2) + x_n(x_{n+1}-x_3) + x_{n+1}(x_1+x_2+x_3)] \text{ (**)}
We have (x1−xn+1)(xn−2−xn+1)≥0⇒xn+12−x1xn+1≥xn−2(xn+1−x1)(x_1 - x_{n+1})(x_{n-2} - x_{n+1}) \ge 0 \Rightarrow x_{n+1}^2 - x_1 x_{n+1} \ge x_{n-2}(x_{n+1} - x_1). Similarly, we construct the other inequalities and add them up, we have
3xn+12≥xn−2(xn+1−x1)+xn−1(xn+1−x2)+xn(xn+1−x3)+xn+1(x1+x2+x3) 3x_{n+1}^2 \ge x_{n-2}(x_{n+1}-x_1) + x_{n-1}(x_{n+1}-x_2) + x_n(x_{n+1}-x_3) + x_{n+1}(x_1+x_2+x_3)
So, it suffices to prove that
3xn+12+6xn+1Sn≥24xn+12⇔xn+1(2Sn−7xn+1)≥0. 3x_{n+1}^2 + 6x_{n+1}S_n \ge 24x_{n+1}^2 \Leftrightarrow x_{n+1}(2S_n - 7x_{n+1}) \ge 0.
Since n≥4n \ge 4 we have 2Sn≥8xn+1≥7xn+12S_n \ge 8x_{n+1} \ge 7x_{n+1} and the last inequality is true.
Thus, the statement is true for n+1n+1. By induction principle, the inequality is true for all n≥8n \ge 8. So (*) holds for all nn.

b) We find the condition for equality in the inequality.
For n=4n=4, equality holds if and only if x1=x2=x3=x4x_1 = x_2 = x_3 = x_4.
For n=5n=5, equality holds if and only if x1=x2=x3=x4=x5x_1 = x_2 = x_3 = x_4 = x_5.
For n=6n=6, equality holds if and only if x1=x4,x2=x5,x3=x6x_1 = x_4, x_2 = x_5, x_3 = x_6.
For n=7n=7, equality holds if and only if x1=x2=x3=x4=x5=x6=x7x_1 = x_2 = x_3 = x_4 = x_5 = x_6 = x_7.
For n=8n=8, equality holds if and only if x1+x5=x2+x6=x3+x7=x4+x8x_1 + x_5 = x_2 + x_6 = x_3 + x_7 = x_4 + x_8.
Consider n≥9n \ge 9, by the proof by induction above, the equality holds if and only if
xn+1=xn−2x1=xn−1x2=xnx3=0andSn2=83Pnwith (∗∗∗) x_{n+1} = x_{n-2}x_1 = x_{n-1}x_2 = x_n x_3 = 0 \quad \text{and} \quad S_n^2 = \frac{8}{3}P_n \quad \text{with } (***)
If n=9n=9 we should have the equality for nn first numbers, as well as we should have x9=x6x1=x7x2=x8x3=0x_9 = x_6x_1 = x_7x_2 = x_8x_3 = 0, that is
{x9=x6x1=x7x2=x8x3=0x1+x5=x2+x6=x3+x7=x4+x8 \begin{cases} x_9 = x_6x_1 = x_7x_2 = x_8x_3 = 0 \\ x_1 + x_5 = x_2 + x_6 = x_3 + x_7 = x_4 + x_8 \end{cases}
If x2=x6=0x_2 = x_6 = 0 or x3=x7=0x_3 = x_7 = 0 then it is easy to see that all other numbers equal to 0; if not all x2,x6x_2, x_6 and x3,x7x_3, x_7 are 0, we can assume that x1=x2=x3=0x_1 = x_2 = x_3 = 0, which leads to the conclusion that the tuple that satisfies the system of conditions is (0,0,0,0,a,a+b,a+b,a+b,b)(0,0,0,0,a,a+b,a+b,a+b,b) and permutations. It is easy to see that the case when all numbers are zero can be included in this case.
If n≥9n \ge 9 then the equality for Sn+12≥83Pn+1S_{n+1}^2 \ge \frac{8}{3}P_{n+1} requires conditions (****). By induction, we can prove that the equality holds only for the tuple
(0,0,0,…,0⏟n−5,a,a+b,a+b,a+b,b) and its permutations. (\underbrace{0,0,0,\dots,0}_{n-5}, a, a+b, a+b, a+b, b) \text{ and its permutations.}

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.