2020 EGMO P2: Sum inequality with permutations

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

2020 EGMO P2: Sum inequality with permutations

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2020 EGMO P2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1547 posts

#1 h Apr 18, 2020, 10:00 PM • 5 Y

Y by anser, itslumi, v4913, megarnie, Rounak_iitr

Find all lists $(x_1, x_2, \ldots, x_{2020})$ of non-negative real numbers such that the following three conditions are all satisfied:

$x_1 \le x_2 \le \ldots \le x_{2020}$ ;
$x_{2020} \le x_1 + 1$ ;
there is a permutation $(y_1, y_2, \ldots, y_{2020})$ of $(x_1, x_2, \ldots, x_{2020})$ such that $\sum_{i = 1}^{2020} ((x_i + 1)(y_i + 1))^2 = 8 \sum_{i = 1}^{2020} x_i^3.$

A permutation of a list is a list of the same length, with the same entries, but the entries are allowed to be in any order. For example, $(2, 1, 2)$ is a permutation of $(1, 2, 2)$ , and they are both permutations of $(2, 2, 1)$ . Note that any list is a permutation of itself.

This post has been edited 1 time. Last edited by alifenix-, Apr 18, 2020, 10:04 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1547 posts

#2 h Apr 18, 2020, 10:30 PM • 6 Y

Y by wu2481632, karitoshi, v4913, Pluto04, Mango247, khina

By rearrangement, we need $\sum_{i = 1}^{2020} ((x_i + 1)(x_{2021 - i} + 1))^2 \le 8 \sum_{i = 1}^{2020} x_i^3.$
Consider the inequality $(a + 1)^2(b + 1)^2 \le 4(a^3 + b^3),$ with $a \le b$ . It can be shown that it is only true when $(a, b) = (0, 1), (1, 2)$ ; we do it using calculus. Evidently $b \in [a, a + 1]$ , so $(a + 1)^2(b + 1)^2 - 4(a^3 + b^3)$ , taking as a function of $b$ , is minimized either when the derivative $\frac{\partial}{\partial b} (a + 1)(b + 1)^2 - 4(a^3 + b^3) = 2(b + 1)(a + 1)^2 - 12b^2 = 0$ or at the endpoints of the interval. The derivative is a quadratic with roots at $b = \frac{(a + 1)^2 \pm \sqrt{(a + 1)^4 + 24(a + 1)^2}}{12},$ and since $b \ge 0$ , we must take the larger root. However, since we need a minimum, the second derivative at this root, $\frac{\partial}{\partial b} 2(b + 1)(a + 1)^2 - 12b^2 = 2(a + 1)^2 - 24b,$ must be positive and thus $b < \frac{(a + 1)^2}{12}$ . However $\frac{(a + 1)^2 + \sqrt{(a + 1)^4 + 24(a + 1)^2}}{12} > \frac{(a + 1)^2}{12}$ , so there are no minimums inside the interval.

If $b = a$ , then we get $(a + 1)^2 (b + 1)^2 - 4(a^3 + b^3) = (a + 1)^4 - 8a^3 = (a - 1)^4 + 8a,$ which is always positive, contradiction. If $b = a + 1$ , then we get $(a + 1)^2(a + 2)^2 - 4(a^3 + (a + 1)^3) = a^2(a - 1)^2,$ so as desired the only pairs $(a, b)$ where this is true are $(0, 1)$ and $(1, 2)$ , and furthermore they are equality cases.

Thus we must have either $x_1 = x_2 = \ldots = x_{1010} = 0, x_{1011} = x_{1012} = \ldots = x_{2020} = 1,$ or $x_1 = x_2 = \ldots = x_{1010} = 1, x_{1011} = x_{1012} = \ldots = x_{2020} = 2.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#3 h Apr 18, 2020, 10:47 PM • 12 Y

Y by tapir1729, alifenix-, Inconsistent, karitoshi, Illuzion, itslumi, v4913, mijail, Pluto04, megarnie, HamstPan38825, khina

alifenix- wrote:

Consider the inequality $(a + 1)^2(b + 1)^2 \le 4(a^3 + b^3),$ with $a \le b$ . It can be shown that it is only true when $(a, b) = (0, 1), (1, 2)$ ; we do it using calculus.

Seems the following is cleaner (remembering that $|a-b| \le 1$ is given):
$a^3+b^3 = (a+b)(a^2-ab+b^2) = (a+b)[(a-b)^2 + ab]$ $\le (a+b)(1+ab) \le \left( \frac{(a+b)+(1+ab)}{2} \right)^2 = \frac{(a+1)^2(b+1)^2}{4}.$

This post has been edited 1 time. Last edited by v_Enhance, Apr 19, 2020, 12:31 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1358 posts

#4 h Apr 18, 2020, 10:49 PM • 2 Y

Y by Mango247, Mango247

v_Enhance wrote:

alifenix- wrote:

Consider the inequality $(a + 1)^2(b + 1)^2 \le 4(a^3 + b^3),$ with $a \le b$ . It can be shown that it is only true when $(a, b) = (0, 1), (1, 2)$ ; we do it using calculus.

Seems the following is cleaner:
$a^3+b^3 = (a+b)(a^2-ab+b^2) = (a+b)[(a-b)^2 + ab]$ $\le (a+b)(1+ab) \le \left( \frac{(a+b)+(1+ab)}{2} \right)^2 = \frac{(a+1)^2(b+1)^2}{4}.$

Oh yeah. Thanks. I forgot about that!

This post has been edited 1 time. Last edited by naman12, Apr 18, 2020, 10:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6877 posts

#5 h Apr 18, 2020, 10:53 PM • 3 Y

Y by v4913, HamstPan38825, asdf334

Isn't it given that $|a-b| \le 1$ for any $a$ and $b$ in the problem statement? (I suppose the quote I had didn't mention that

)

This post has been edited 1 time. Last edited by v_Enhance, Apr 18, 2020, 10:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

691 posts

#6 h Apr 19, 2020, 3:34 AM • 7 Y

Y by CyclicConcaveTriangle, karitoshi, GorgonMathDota, Sugiyem, itslumi, Pluto04, ILOVEMYFAMILY

Personally, i think this is a lot easier than 01, solved #01 much slower than this?
Since there exists a permutation $\{y_i\}$ that satisfies such condition. By rearrangement Inequality, we have
$\sum_{i = 1}^{2020} ((x_i + 1)(x_{2021 - i} + 1))^2 \le 8 \sum_{i = 1}^{2020} x_i^3$ $\textbf{Main Claim.}$ For any nonnegative reals $x \ge y$ such that $x - y \le 1$ , then
$4(x^3 + y^3) \le ((x+1)(y+1))^2$ $\textit{Proof.}$ Notice that
$x^3 + y^3 = (x + y)(x^2 - xy + y^2) = (x+y)((x-y)^2 + xy) \le (x+y)(xy + 1) \le \frac{((x+1)(y+1))^2}{4}$ Equality holds if and only if $xy + 1 = x + y$ and $x = y + 1$ , which gives us $(2,1)$ and $(1,0)$ .
Therefore, applying this to the original statement, we have that $x_i \{ 0, 1, 2 \}$ for each $i \in [1,2020]$ .
Now, suppose that $x_1 = 0$ , this gives us $x_{2020} = 1$ , forcing all the others $(x_i, x_{2020 - i})$ to be $(0,1)$ as well, giving $(0,0,0,\dots,0,1,1,\dots,1)$ as a solution.
Suppose that $x_1 = 1$ , this gives $x_{2020} = 2$ , forcing all the others $(x_i, x_{2020 - i})$ to be $(1,2)$ as well, giving $(1,1,1,\dots,1,2,2,\dots,2)$ as a solution.

Therefore, the solutions are
$x_1 = x_2 = \dots = x_{1010} = 1 \ \text{and} \ x_{1011} = x_{1012} = \dots = x_{2020} = 2$ and
$x_1 = x_2 = \dots = x_{1010} = 0 \ \text{and} \ x_{1011} = x_{1012} = \dots = x_{2020} = 1$
Remark. At first i tried to use the fact $|x - y| \le 1$ to prove $(x-1)^4 + (y - 1)^4 + 8(x+y) \ge (x+y+2)^2$ , but when i square the initial condition (lol) and look back at the identity $x^3 + y^3$ , solved this really fast accidentally.

This post has been edited 2 times. Last edited by IndoMathXdZ, Apr 19, 2020, 3:47 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1358 posts

#7 h Apr 19, 2020, 3:37 AM • 5 Y

Y by Inconsistent, vsamc, user1729, Aryan-23, ehuseyinyigit

Yeah. I didn't solve this very fast. Took me wayyyyy too much time (like > 30 minutes):
We have the following
Claim. For $0\leq x\leq y\leq x+1$ , we have $4(x^3+y^3)\leq (x+1)^2(y+1)^2$ . Furthermore, equality holds for $(x,y)=(0,1),(1,2)$ .
Proof. We start with defining the function
$f(y)=(x+1)^2(y+1)^2-4x^3-4y^3=-4y^3+(x+1)^2(y^2+2y+1)-4x^3$ Now, we expand to get
$f(y)=-4y^3+(x+1)^2y^2+2(x+1)^2y+(x+1)^2-4x^3$ Now, we note that
$f'(y)=-12y^2+2(x+1)^2y+2(x+1)^2$ We note that
$f'(x)=-12x^2+2(x+1)^2x+2(x+1)^2=2x^3-6x^2+6x+2=2(x-1)^3+4$ and
$f'(x+1)=-12(x+1)^2+2(x+1)^3+2(x+1)^2=2(x+1)^2(x-4)=2x^3-4x^2-14x-8$ Now, if $x\geq 4$ , then $f(x)$ is decreasing, so it suffices to check $f(x)$ on its bounds. For $x<4$ , we get that there is exactly one root in $[x,x+1]$ of $f'(x)$ . We can check this is a maximum as
$f'\left(\dfrac{(x+1)^2}{12}\right)=-12\left(\dfrac{(x+1)^2}{12}\right)^2+2(x+1)^2\left(\dfrac{(x+1)^2}{12}\right)+2(x+1)^2$ Simplifying the first two, we get
$f'\left(\dfrac{(x+1)^2}{12}\right)=\dfrac{(x+1)^4}{12}+2(x+1)^2>0$ so thus we get that the root of $f'(x)$ is greater than $\dfrac{(x+1)^2}{12}$ . Now, we get that if this root is $r$ , it is a maximum if and only if $f''(r)>0$ . However, we have
$f''(r)=-24r+(x+1)^2>0$ as $r>\dfrac{(x+1)^2}{12}$ . Thus, in both cases where $x\geq 4$ and $x<4$ , we have that the minimum of $f(x)$ occur on the bounds. Now, the rest is easy to check. We get
$f(x)=(x+1)^4-8x^3=(x-1)^4+8x>0$ as we can easily check that $(x+1)^4-(x-1)^4=8x^3+8x$ . Thus, we also have
$f(x+1)=(x+1)^2(x+2)^2-4x^3-4(x+1)^3=(x+1)^2(x^2)-4x^3=(x-1)^2x^2\geq 0$ with equality only for $x=0,1$ . Thus, the claim has been proved. $\blacksquare$ .

Now, we note by the Rearrangement Inequality, we get
$4\sum_{i=1}^{2020}(x_i^3+x_{2021-i}^3)=8\sum_{i=1}^{2020}x_i^3=\sum_{i=1}^{2020}(x_i+1)^2(y_i+1)^2\geq\sum_{i=1}^{2020}(x_i+1)^2(x_{2021-i}+1)^2$ However, we have that applying our claim on $x_i,x_{2020-i}$ for all $1\leq i\leq 2020$ , we get
$4\sum_{i=1}^{2020}(x_i^3+x_{2021-i}^3\leq \sum_{i=1}^{2020}(x_i+1)^2(x_{2021-i}+1)^2$ with equality only for $x_1=x_2=\cdots=x_{1010}=0,1$ and $x_{1011}=x_{1012}=\cdots=x_{2020}$ . Thus, we can define it as:
$\boxed{x_k=\begin{cases}0,1&k=1\\x_1&2\leq k\leq 1010\\x_1+1&1011\leq k\leq 2020\end{cases}}$ I hate not being able to see like v_enhance.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1595 posts

#8 h Apr 19, 2020, 9:59 AM • 1 Y

Y by Tintarn

Here is a cleaner way to prove the inequality.

The answer is $(0,0,\hdots,0,1,1,\hdots,1)$ and $(1,1,\hdots,1,2,2,\hdots,2)$ where each numbers appear $1010$ times. This is easily seen to work so we prove that these are all solutions. Consider the following.

Claim: For any reals $a,b$ such that $|a-b|\leq 1$ , we have $(a+1)^2(b+1)^2\geq 4(a^3+b^3)$ , with equality at $(0,1)$ , $(1,2)$ .

Proof: We first reduce this to one-var. Set $a=t+\delta$ and $b=t-\delta$ where $\delta\in (0,\tfrac 12]$ . We have
$\text{LHS} = ((t+1)^2-\delta^2)^2 \geq \left((t+1)^2-\tfrac{1}{4}\right)^2.$ Moreover,
$\text{RHS} = 4((t+\delta)^3 + (t-\delta)^3)= 8t(t^2+3\delta^2) \leq 8t\left(t^2+\tfrac{3}{4}\right)$ Hence it suffices to prove that $\left((t+1)^2-\tfrac{1}{4}\right)^2\geq 8t^3+6t$ , which could be easily expanded to $\left(t-\tfrac{1}{2}\right)^2\left(t-\tfrac{3}{2}\right)^2\geq 0$ . The equality case can easily be reverse-engineered. $\blacksquare$

Applying the claim with $(x_i, y_i)$ and sum up, we get that
$\sum_{i=1}^{2020}((x_i+1)(y_i+1))^2\geq 8\sum_{i=1}^{2020}x_i^3.$ The equality case occurs if and only if $(x_i, y_i) = (0,1), (1,2)$ for each $i$ . It's easy to see that they must be $(0,1)$ or $(1,2)$ for all $i$ . Moreover, each number appears in $x_1,x_2,\hdots,x_{2020}$ exactly $1010$ times. Hence there are two such lists.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

30244 posts

arqady

#9 h Apr 19, 2020, 10:45 AM • 1 Y

Y by Mango247

It's enough to prove that $(a+1)^2(b+1)^2\geq4(a^3+b^3),$ where $a$ and $b$ are non-negatives such that $(a-b)^2\le1.$
Indeed, let $a+b=2u$ and $ab=v^2$ .
Thus, $4u^2-4v^2\leq1$ and we need to probe that $(v^2+2u+1)^2\geq4(8u^3-6uv^2)$ or
$v^4+(28u+2)v^2+(2u+1)^2\geq32u^3,$ for which it's enough to prove that
$v^4+(28u+2)v^2+(2u+1)^2\geq8u(4v^2+1)$ or
$v^4-2(2u-1)v^2+(2u-1)^2\geq0$ or $(v^2-2u+1)^2\geq0$ and from here we can get the equality cases occurring.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1247 posts

#10 h Apr 20, 2020, 10:40 PM

Y by

Solved with TheUltimate123 and eisirrational.

The answer is $(\underbrace{0,\dots,0}_{1010 \ \text{0's}}, \underbrace{1,\dots,1}_{1010 \ \text{1's}})$ and $(\underbrace{1,\dots,1}_{1010 \ \text{1's}}, \underbrace{2,\dots,2}_{1010 \ \text{2's}})$ . These can be easily checked to work, so we now show uniqueness.

By the Rearrangement Inequality, we have that
$8 \sum_{i = 1}^{2020} x_i^3 = \sum_{i = 1}^{2020} ((x_i + 1)(y_i + 1))^2 \geq \sum_{i = 1}^{2020} ((x_i + 1)(x_{2021-i} + 1))^2.$
We, in fact, show the reverse inequality in the following claim.

Claim. For all reals $a \leq b \leq a+1$ , we have $8(a^3+b^3) \leq 2(a+1)^2(b+1)^2$ . Moreover, equality holds when $(a,b) = (0,1)$ or $(1,2)$ .

Proof. Verify that
$(a+1)^2(b+1)^2 - 4(a^3+b^3) = (a-1)^2(b-1)^2 + 4(a+b)(1-(a-b)^2) \geq 0$ as desired.

Finally, apply the claim to $(a,b) = (x_i, x_{2021-i})$ and sum the resulting inequalities to show that
$8 \sum_{i = 1}^{2020} x_i^3 \leq \sum_{i = 1}^{2020} ((x_i + 1)(x_{2021-i} + 1))^2.$ So equality must hold, as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#11 h Apr 22, 2020, 6:07 AM

Y by

Claim: If $0\le b-a\le 1$ , then $(a+1)^2(b+1)^2 \ge 4(a^3+b^3)$ , with equality iff $(a,b)=(0,1),(1,2)$ .

Proof: We see that
$\begin{align*} 4(a^3+b^3) &= 4(a+b)(a^2-ab+b^2) = 4(a+b)[(b-a)^2 + ab] \\ &\le 4(a+b)(1+ab) = (2a+2b)(2+2ab) \le (a+b+1+ab)^2 \\ &=(a+1)^2(b+1)^2. \end{align*}$ Equality is achieved when $b-a=1$ and $a+b=1+ab$ simultaneously, i.e. $(a,b)=(0,1),(1,2)$ . $\square$

By the Rearrangement inequality, the minimum LHS is achieved when we pair the smallest elements with the largest available:
$\sum_{i=1}^{2020} ((x_i+1)(y_i+1))^2 \ge \sum_{i=1}^{2020} ((x_i+1)(x_{2021-i}+1))^2.$ Since all the $x_i$ 's are within 1 of each other, we apply the claim to get
$((x_i+1)(x_{2021-i}+1))^2 \ge 4(x_i^3+x_{2021-i}^3).$ Sum the above cyclically to conclude that the LHS is at least the RHS in the third condition. Equality is achieved when $(x_i,x_{2021-i}) = (0,1)\text{ or }(1,2)$ for all $i$ . Note that we cannot have both combinations in a single working tuple, since all the $x_i$ 's are within 1 of each other. Hence, the two equality cases are
$(x_1,\ldots,x_{2020}) = (0,\ldots,0,1,\ldots,1), \ (1,\ldots,1,2,\ldots,2),$ where each of the two tuples above has 1010 of each number.

Remarks

This post has been edited 1 time. Last edited by pad, Apr 22, 2020, 6:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeronimoStilton

1521 posts

GeronimoStilton

#12 h Apr 26, 2020, 1:00 PM

Y by

The two lists satisfying these criteria are $(1,1,\dots, 1,2,2,\dots, 2)$ where there are $1010$ of each of $1$ and $2$ and the similarly defined $(0,0,\dots, 0,1,1,\dots, 1)$ . It is easy to check that both of these work. Now, consider some satisfactory sequence.

By Rearrangement Inequality, we have
$\sum_{i=1}^{2020} (x_i+1)^2(y_i+1)^2 \ge \sum_{i=1}^{2020} (x_i+1)^2(x_{2021-i}+1)^2 = 2\sum_{i=1}^{1010} (x_i+1)^2(x_{2021-i}+1)^2.$ Clearly, there exists some $i$ with
$(x_i+1)^2(x_{2021-i}+1)^2 \le 4(x_i^3+x_{2021-i}^3).$ Let $x_i+1=a,x_{2021-i}+1=b$ . Note that $b \le 1+a$ . We have
$a^2b^2\le 4(a^3-3a^2+3a-1+(b-1)^3).$ Observe that the function
$f(b) = a^2b^2-(b-1)^3$ has
$f’(b) = 2a^2b - 3(b-1)^2 \ge 2a^2b-3a^2 = a^2(2b-3),$ so $f$ certainly has nonnegative slope for $b \ge 3/2$ . For $b \le 3/2$ , we get $a^2b^2 \ge 9/4$ and $4(a-1)^3 + 4(b-1)^3 \le 1$ , a contradiction.

Thus, we ought to check this inequality at just $b=a+1$ and $b=a$ . At $b=a$ we get
$a^4\le 8(a-1)^3 = (2a-2)^3.$ Note that the function $f(a) = a^4-(2a-2)^3$ is convex because $f''(a) = 12a^2 - 48(a-1) = 12(a^2-4a+4)$ is nonnegative. Thus, this inequality can never be satisfied because $1^4 > 8(1-1)^3$ and $f’(1) = 4\cdot 1^3-24(1-1)^2 > 0$ . That is, we now only need to check $b=a+1$ . Plug in $b=a+1$ to obtain
$a^4+2a^3+a^2 = a^2(a+1)^2 \le 4(a-1)^3 + 4a^3 = 8a^3 - 12a^2+12a-4.$ Rearrange to get
$0 \ge a^4-6a^3+13a^2-12a+4 = (a-2)(a^3-4a^2+5a-2) = (a-2)^2(a^2-2a+1) = (a-1)^2(a-2)^2.$ Note that this inequality is always at most an equality; this means that each $x_i+1$ is one of $1$ or $2$ . But clearly the information about $b$ forces either all $x_i$ with $1\le i \le 1010$ to be $0$ or all $1$ . This yields the two claimed solutions above.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

651 posts

#13 h May 13, 2020, 1:56 AM • 1 Y

Y by Gerninza

My solution is same as everyone done . BUT MY Solution to $4(x^3+y^3)\le (x+1)^2(y+1)^2)$ is bit different . Here it is -

$(x+1)^2(y+1)^2$

$=(xy+x+y+1)^2$

$\ge (xy+x+y +(x-y)^2)^2$ [cause $|x-y|\le 1$ ].

$=(x+y +(x^2+y^2-xy)^2$

$\ge (x+y)(x^2+y^2-xy).4$ [AM-GM]

$=4(x^3+y^3)$ .

Obviously equality holds for $(x-y)^2=1$ and $x^2+y^2-xy =x+y$ .

This post has been edited 1 time. Last edited by ftheftics, May 13, 2020, 1:56 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

558 posts

#14 h Jul 5, 2020, 7:16 PM • 4 Y

Y by AlastorMoody, Pluto04, kamatadu, Mango247

So troll

:mad:

We claim that the only solutions are $\boxed{x_k=\begin{cases}0,1&k=1\\x_1&2\leq k\leq 1010\\x_1+1&1011\leq k\leq 2020\end{cases}}$
Invoking Rearrangement inequality, we have $8 \sum_{i = 1}^{2020} x_i^3 = \sum_{i = 1}^{2020} ((x_i + 1)(y_i + 1))^2 \geq \sum_{i = 1}^{2020} ((x_i + 1)(x_{2021-i} + 1))^2.$ .

We now present a crucial claim .

$\mathbf{Lemma}$ Consider non-negative reals $a \leq b$ with $a-b \leq 1$ . We claim the following inequality holds
$(a + 1)^2(b + 1)^2 \geq 4(a^3 + b^3)$
with equality iff $(a,b)=(1,0) \text { or} (2,1)$

$\mathbf{Proof :}$ We have
$\left((a+1)(b+1) \right)^2 = \left((a+b) +(ab+1)\right)^2 \geq 4(a+b)(ab+1) \geq 4(a+b)(ab+ (a-b)^2) = 4(a+b)(a^2+ab+b^2) = 4(a^3+b^3)$ Equality occurs when $a=b+1$ and $a+b=ab+1$ .

Now we are ready to finish .
Note that , from the claim we have,
$\sum_{i = 1}^{2020} ((x_i + 1)(x_{2021-i} + 1))^2 \geq 8\sum_{i = 1}^{2020} x_i^3$ .

So we have the forementioned solutions as desired as equality must hold in all the estimates we used .
$\blacksquare$ .

This post has been edited 2 times. Last edited by Aryan-23, Jul 5, 2020, 7:24 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

141 posts

#15 h Nov 26, 2020, 3:41 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

46 posts

#16 h Nov 15, 2021, 12:55 PM

Y by

We know that $(x_1+1)^2\leq (x_2+1)^2 \leq \cdots \leq (x_{2020}+1)^2$ . Now Rearrangement inequality gives us $\sum_{i = 1}^{2020} ((x_i + 1)(y_i + 1))^2 \geq \sum_{i = 1}^{2020} ((x_i + 1)(x_{2020-i} + 1))^2$ Now I'll prove that for each $1\leq i \leq 1010$ e have $((x_i + 1)(x_{2020-i} + 1))^2+((x_{2020-i} + 1)(x_i + 1))^2 \geq 8(x_i^3+x_{2020-i}^3) (*)$ and when summing all of these up we would get $\sum_{i = 1}^{2020} ((x_i + 1)(x_{2020-i} + 1))^2 \geq 8 \sum_{i = 1}^{2020} x_i^3$ so the only solutions will be the equality cases in $(*)$ .

Now let's for brevity have $x_i=x$ and $x_{2020-i}=y$ and we also know that $x_{2020-i}-x_i=y-x\leq 1$ . Now let $y-x=k$ , so we know that $0\leq k\leq 1$ . Now $(*)$ transforms into proving $(x+1)^2(x+1+k)^2 \geq 4(x^3+(x+k)^3) \Leftrightarrow$ $(x+1)^4+2(x+1)^3k+(x+1)^2k^2 \geq 4(x^3+x^3+3x^2k+3xk^2+k^3) \Leftrightarrow$ $x^4+4x^3+6x^2+4x+1+2x^3k+6x^2k+6xk+2k+x^2k^2+2xk^2+k^2\geq$ $\geq 8x^3+12x^2k+12xk^2=4k^3 \Leftrightarrow$ $x^4+2x^3(k-2)+x^2(6-6k+k^2)+x(4+6k-10k^2)+(k^2+2k+1-4k^3)\geq 0$ $x^2(x^2+2x(k-2)+(k-2)^2)+x^2(6-6k+k^2-(k-2)^2)+x(4+6k-10k^2)+(k^2+2k+1-4k^3)\geq 0$ $x^2(x+(k-2))^2+2x^2(1-k)+x(k-1)(-10k-4)+(k-1)(-4k^2-3k-1)\geq 0$ Now we have the following inequalities (for $0\leq k\leq 1$ )
$x^2(x+(k-2))^2\geq 0$ $2x(1-k)\geq 0$ $x(k-1)(-10k-4)\geq 0$ $(k-1)(-4k^2-3k-1)\geq 0$ There is an equality in the last one only when $k=1$ , so we get that we should have $k=1$ .Now $(*)$ transforms into $x^2(x-1)^2\geq 0$ and equality holds only when $x=0;1$ .

We got that in $((x_i + 1)(x_{2020-i} + 1))^2+((x_{2020-i} + 1)(x_i + 1))^2 \geq 8(x_i^3+x_{2020-i}^3)$ equality holds only when $x_i=1$ and $x_{2020-i} = 2$ or when $x_i=0$ and $x_{2020-i}=1$ . Together with the constraints in the statement we get that the only solutions are $x_1=x_2=\cdots =x_{1010}=0 ; x_{1011}=\cdots = x_{2020}=1$ $x_1=x_2=\cdots =x_{1010}=1 ; x_{1011}=\cdots = x_{2020}=2$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#17 h Apr 9, 2022, 9:02 PM • 1 Y

Y by centslordm

Yet another proof of the main inequality

The answer is $(0,\ldots,0,1,\ldots,1)$ and $(1,\ldots,1,2,\ldots,2)$ , where both tuples contain exactly $1010$ ones. We can verify that these work by letting $(y_1,\ldots,y_{2020})$ be the reverse of $(x_1,\ldots,x_{2020})$ .

The key inequality is the following bound:
$\sum_{i=1}^{2020}(x_i+1)^2(x_{2020-i}+1)^2\geq 8\sum_{i=1}^{2020} x_i^3.$ It suffices to "break up" this summation and prove
$(x_i+1)^2(x_{2020-i}+1)^2\geq 4x_i^3+4x_{2020-i}^3.$ Let $a=x_i$ and $b=x_{2020-i}$ , so $a \leq b \leq a+1$ . The inequality becomes $(a+1)^2(b+1)^2 \geq 4a^3+4b^3 \iff (a+1)^2(b+1)^2-4a^3-4b^3 \geq 0$ . Fix $b$ and let $f(a)$ denote the value of the expression that we want to prove is nonnegative over the interval $I=[0,1] \cap [b-1,b]$ .
We can compute $f'(a)=2(b+1)^2(a+1)-12a^2$ . Since $f'(0)=2(b+1)^2>0$ and $f'(-\infty)=-\infty<0$ , it follows that there is exactly one nonnegative root of $f'$ (Descartes' rule of signs works too!). Hence there is at most one turning point of $f$ in $I$ , where $f$ must go from increasing to decreasing. As such, $f$ attains its minimum at an endpoint of $I$ . We have
$\begin{align*} f(b)&=(b+1)^4-8b^3=b^4-4b^3+6b^2+4b+1=(b-1)^4+8b^3>0\\ f(b-1)&=b^2(b+1)^2-4b^3-4(b-1)^3=(b-2)^2(b-1)^2\geq 0\\ f(0)&=(b+1)^2-4b^3=(1-b)(4b^2+3b+1)\geq 0~\forall b \leq 1,\\ \end{align*}$ hence $f(a)$ is indeed nonnegative for $a \in I$ , and is zero only if $(a,b)=(0,1)$ or $(a,b)=(1,2)$ , by looking at the equality cases.
Then by rearrangement, for any permutation $(y_1,\ldots,y_{2020})$ , we have
$\sum_{i=1}^{2020}(x_i+1)^2(y_i+1)^2\geq \sum_{i=1}^{2020}(x_i+1)^2(x_{2020-i}+1)^2\geq 8\sum_{i=1}^{2020} x_i^3.$ It is clear that we can't have both of our equality cases hold at the same time (since that makes $x_1<x_{2020}+1$ ), so we extract the desired solution set. $\blacksquare$

This post has been edited 3 times. Last edited by IAmTheHazard, Jan 9, 2023, 3:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8863 posts

#18 h Jan 7, 2023, 4:03 AM • 1 Y

Y by Mango247

The key is to use the following equaltiy:

Claim. $(x+1)^2(y+1)^2 \geq 4(x^3+y^3)$ as long as $|x-y| \leq 1$ with equality at $(0, 1)$ and $(1, 2)$ .

We can use the inequality $(x-y)^2 \leq 1$ , and substitute $a = x+y, b = xy$ , so that the given equation reduces to $(a+b+1)^2 \geq 4a(b+1).$ This can just be done by considering $\Delta_a$ for the resulting quadratic in $a$ , details omitted. $\blacksquare$

For the final part, we can use Rearrangement in the form $\sum_{i=1}^{2020} (x_i+1)^2(y_i+1)^2 \geq \sum_{i=1}^{2020} (x_i+1)^2(x_{2021-i}+1)^2 \geq 8\sum_{i=1}^{1010} (x_i^3+x_{2021-i}^3).$ Thus, equality must hold everywhere, which implies that $(x_i, x_{2021-i}) = (0, 1)$ or $(1, 2)$ . Obviously the solutions must all come from one of these combinations, so only $(0, 0, \cdots, 0, 1, 1, \cdots, 1)$ and $(1, 1, \cdots, 1, 2, 2, \cdots, 2)$ , where there are 1010 of each number, work.

This post has been edited 1 time. Last edited by HamstPan38825, Jan 7, 2023, 4:03 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

795 posts

#19 h Oct 12, 2023, 4:19 AM

Y by

Our given condition can be rewritten as
$\sum_{i = 1}^{2020} ((x_i + 1)(y_i + 1))^2 = 4 \sum_{i = 1}^{2020} (x_i^3 + y_i^3).$
Due to the order we are given, Rearrangement inequality implies
$\sum_{i = 1}^{2020} ((x_i + 1)(x_{2021-i} + 1))^2 \leq 4 \sum_{i = 1}^{2020} (x_i^3 + x_{2021-i}^3).$
However, comparing each individual summand, we notice the inequality
$\left((a+1)(b+1)\right)^2 \ge \left(2 \sqrt{(ab+1)(a+b)}\right)^2 = 4(a+b)(ab+1) \ge 4(a+b)(ab+(a-b)^2) = 4(a^3+b^3),$
where $a = x_i$ and $b = x_{2021-i}$ for simplicity, and $(a-b)^2 \leq 1$ by our second condition. Hence we must have the equality case, or
$\begin{align*} (a-b)^2 = 1 &\implies a = b \pm 1 \\ ab+1 &= a+b, \end{align*}$
from which we get the pairs $(0, 1)$ and $(1, 2)$ . Thus our possible sequences are
$\boxed{a_1 = a_2 = \ldots = a_{1010} = 0, \quad a_{1011} = a_{1012} = \ldots = a_{2020} = 1}$ $\boxed{a_1 = a_2 = \ldots = a_{1010} = 1, \quad a_{1011} = a_{1012} = \ldots = a_{2020} = 2}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2534 posts

#20 h Oct 16, 2023, 2:38 AM

Y by

The answer is $(\underbrace{0,\dots,0}_{1010 \ \text{0's}}, \underbrace{1,\dots,1}_{1010 \ \text{1's}})$ and $(\underbrace{1,\dots,1}_{1010 \ \text{1's}}, \underbrace{2,\dots,2}_{1010 \ \text{2's}})$ . These can be easily checked to work, so now we prove that these are the only solutions

Claim: For reals $0 \le x \le y \le x+1$ , we have $2(x+1)^2(y+1)^2 \ge 8(x^3+y^3)$ , equality at $(x,y)=(0,1), (1,2)$ .

Proof: Expansion gives

$\begin{align*} &(x+1)^2(y+1)^2-4(x^3+y^3) \\ = \ &(x-1)^2(y-1)^2+4(x+y)(xy+1)-4(x^3+y^3) \\ = \ &(x-1)^2(y-1)^2 + 4(x+y)(xy+1-(x^2+y^2-xy)) \\ = \ &(x-1)^2(y-1)^2 + 4(x+y)(1-(x-y)^2) \ge 0. \ \square \end{align*}$
Substituting in $(x,y)=(x_i, x_{2021-i})$ and summing, we get

$\sum_{i=1}^{2020} ((x_i-1)(x_{2021-i}-1))^2 \ge 8 \sum_{i = 1}^{2020} x_i^3$
However, by the Rearrangement Inequality, we have

$\sum_{i=1}^{2020} ((x_i-1)(x_{2021-i}-1))^2 \le \sum_{i = 1}^{2020} ((x_i + 1)(y_i + 1))^2 = 8 \sum_{i = 1}^{2020} x_i^3$
Thus, we must have the equality case, meaning $(x_i, x_{2021-i})=(0,1), (1,2)$ for $1 \le 1 \le 1010$ , giving us our two solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

60 posts

#21 h Nov 24, 2023, 9:32 PM

Y by

Note that
$\sum_{i=1}^{2020}{(x_i+1)^2(x_{2021-i}+1)^2} \leq \sum_{i=1}^{2020}{(x_i+1)^2(y_i+1)^2}$ from rearrangement inequality. We claim that
$8(x^3+y^3) \leq 2(x+1)^2(y+1)^2$ with equality case when they're both $1$ , if $(x-y)^2\leq 1$ . From, $(x-y)^2\leq 1$ , we get
$(x-y)^2\leq 1 \implies x^2+y^2 \leq 1+2xy \implies x^3+y^3 \leq (1+xy)(x+y)$ Note that
$0\leq(x-1)^2(y-1)^2 \implies 4(1+xy)(x+y) \leq (x+1)^2(y+1)^2$ completing the proof. The equality case of such inequality is when one of them is $1$ and the other is $1$ away, giving $(0,1)$ and $(1,2)$ . Thus, our only two sequences are $x_{i} = (0,1)$ , $i \in \{1, 2, \cdots, 1010\}$ , $x_{i} = (1,2)$ , $i \in \{1011, 1012, \cdots, 2020\}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1745 posts

OronSH

#22 h Jan 13, 2024, 5:37 PM

Y by

We first prove that if nonnegative $x,y$ satisfy $(x-y)^2\le 1,$ then $((x+1)(y+1))^2 \ge 4(x^3+y^3).$ To do this, let $x+y=s,xy=p$ and our condition is $s^2\le 4p+1.$ We wish to show that $s^2+p^2+14sp+2s+2p+1 \ge 4s^3.$ From our condition we may instead consider $s^2+p^2+14sp+2s+2p+1 \ge 16sp+4s,$ which implies the result. However this simplifies to $(p-s+1)^2 \ge 0,$ which is clear, and equality holds iff both $(x-y)^2=1$ and $(xy-x-y+1)^2=0,$ that is, either $x=1$ or $y=1.$ Thus equality holds when $(x,y)=(0,1),(1,0),(1,2),(2,1).$

Now by Rearrangement Inequality on our original expression, we see that $\sum_{i=1}^{2020}((x_i+1)(y_i+1))^2 \ge \sum_{i=1}^{2020}((x_i+1)(x_{2021-i}+1))^2.$ Now letting $x_i=x$ and $x_{2021-i}=y,$ since we have $|x_i-x_{2021-i}| \le |x_{2020}-x_1|\le 1,$ we see that $((x_i+1)(x_{2021-i}+1))^2 \ge 4(x_i^3+x_{2021-i}^3).$ Summing this across all $1 \le i \le 2020,$ we see that $\sum_{i=1}^{2020}((x_i+1)(x_{2021-i}+1))^2 \ge 8\sum_{i=1}^{2020} x_i^3,$ and equality holds iff each pair of $(x_i,x_{2021-i})$ is one of the four we found above. From here we notice that we cannot have both a $0$ and a $2,$ and since the sequence is increasing we get that the only possibilities are $x_1=x_2=\cdots=x_{1010}=0,x_{1011}=x_{1012}=\cdots=x_{2020}=1$ and $x_1=x_2=\cdots=x_{1010}=1,x_{1011}=x_{1012}=\cdots=x_{2020}=2.$

This post has been edited 1 time. Last edited by OronSH, Jan 13, 2024, 5:40 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1324 posts

#23 h Jan 23, 2024, 3:24 PM • 1 Y

Y by ehuseyinyigit

We will first show that $4(x^3 + y^3) \leq ((x + 1)(y + 1))^2$ , if $|x-y| \leq 1$ .

$(xy + x + y + 1)^2 = ((x + 1)(y + 1))^2$ $= (xy + x + y + 1)^2 \geq (xy + x + y + (x - y)^2)^2$ $= (x^2 - xy + x + y + y^2)^2 \geq 4(x^2 - xy + y^2)(x + y)$ $= 4(x^3 + y^3)$ $\implies 4(x^3 + y^3) \leq ((x + 1)(y + 1))^2$

Then by Rearrangement Inequality,
$\newline$
$\sum_{i = 1}^{2020} ((x_i + 1)(x_{2020-i} + 1))^2 \leq \sum_{i=1}^{2020} ((x_i + 1)(y_i + 1))^2 = \sum_{i = 1}^{2020} x_i^3$ Which implies that this is the equality case of the Rearrangement Inequality, so the list $x_i$ either consists of $1010$ $0$ 's and $1010$ $1$ 's, or $1010$ $1$ 's and $1010$ $2$ 's.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

353 posts

#24 h Aug 26, 2024, 5:46 PM

Y by

Feels more like an equality problem instead of manipulation. This took way too long, why didn't I try the obvious thing to do first :stretcher:

:stretcher:

We will prove that the only solutions $(x_1, x_2, \dots, x_{2020})$ is the multiset containing $1010$ copies of $0$ and $1$ , and the multiset containing $1010$ copies of $1$ and $2$ , which are easily shown to work. We begin with the following claim:

$\textbf{Claim 1.}$ If $|a - b| \le 1$ , then $(a + 1)^2 (b + 1)^2 \le 4(a^3 + b^3)$ .
Proof. Let $a + b = 2u$ , $ab = v^2$ , we have
$|a - b| \le 1 \iff (a + b)^2 - 4ab \le 1 \iff v^2 \ge \dfrac{4u^2 - 1}{4}$ and we wish to show
$(a + 1)^2 (b + 1)^2 \ge 4(a^3 + b^3) \iff (ab + a + b + 1)^2 \ge 4(a + b)[(a + b)^2 - 3ab] \iff (2u + v^2 + 1)^2 \ge 8u(4u^2 - 3v^2).$ Now utilizing the earlier condition we have $(2u + v^2 + 1)^2 \ge \left( \dfrac{4u^2 + 8u + 3}{4} \right)^2$ and $8u \left( \dfrac{4u^2 + 3}{4}\right) \ge 8u(4u^2 - 3v^2)$ so it suffices to prove that
$\left( \dfrac{4u^2 + 8u + 3}{4} \right)^2 \ge 8u \left( \dfrac{4u^2 + 3}{4}\right) \iff 16u^4 - 64u^3 + 88u^2 - 48u + 9 \ge 0 \iff (2u - 1)^2 (2u - 3)^2 \ge 0$ which is true. Equality cases occur at $u = 1/2, 3/2$ , and reverse-engineering the original pairs we get $(a, b) = (0, 1), (1, 2)$ and permutations.

Now returning to the original problem, note that by Chebyshev (also extended Rearrangement) we obtain
$8 \sum_{i = 1}^{2020} x_i^3 \ge \sum_{i = 1}^{2020} (x_i + 1)^2 (x_{2021 - i} + 1)^2$ but summing $\textbf{Claim 1.}$ over all $i$ on ordered pairs $(x_i, x_{2021 - i})$ yields the same inequality with an inverted sign. Hence, equality must hold, which easily generates the solution sets claimed earlier.

This post has been edited 2 times. Last edited by blueprimes, Aug 27, 2024, 11:45 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

757 posts

#25 h Sep 6, 2024, 10:00 PM

Y by

What a missed solve ;-;
Subjective Rating (MOHs) $\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8 posts

#26 h Dec 16, 2024, 7:28 PM • 1 Y

Y by vi144

mostly similar to other solutions but instead of rearrangements we use substitutions

This post has been edited 1 time. Last edited by mariairam, Dec 16, 2024, 7:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

627 posts

#27 h Apr 25, 2025, 3:47 PM

Y by

I claim the inequality $((x + 1)(y + 1))^2 \leq 4 (x^3 + y^3)$ . We have that $x^3 + y^3 = (x + y)((x - y)^2 + xy) \leq (x + y)(1 + xy) \leq\left(\frac{(x + y)^2 + (1 + xy)^2}{2}\right)^2 = \frac{(x + 1)^2(y + 1)^2}{4}.$ Equality holds if and only if $x - y = 1, x + y = 1 + xy.$ Hence, $(x, y) = (0, 1), (1, 2).$

Hence,
$8 \sum_{i = 1}^{2020} x_i^3 = \sum_{i = 1}^{2020} ((x_i + 1)(y_i + 1))^2 \geq \sum_{i = 1}^{2020} ((x_i + 1)(x_{2021 - i} + 1))^2 \geq 8\sum_{i = 1}^{2020} x_i^3$ where the 1st inequality is by rearrangement, and 2nd is by our claim.

Hence, equality can only occur when they are: $(0, ..., 0, 1, ..., 1), (1, ..., 1, 2, ..., 2),$ where each one appears 1010 times.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

575 posts

#28 h Apr 28, 2025, 6:31 PM

Y by

Observe that $|x_i-y_i| \leq 1$ we have $4x_i^3+4y_i^3 = 4(x_i+y_i)((x_i-y_i)^2+x_iy_i) \leq 4(x_i+y_i)(1+x_iy_i) \leq ((1+x_i)(1+y_i))^2$ by AM-GM. Summing yields equality holds, so $|x_i-y_i| = 1$ and $x_i+y_i=1+x_iy_i \implies (x_i-1)(y_i-1)=0.$ So $(x_i, y_i) = (1, 0), (1, 2).$ Hence the solutions are the first $1010$ being $0$ and the rest being $1,$ or the first $1010$ being $1$ and the rest being $2.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math-olympiad-clown

30 posts

math-olympiad-clown

#29 h Apr 29, 2025, 2:44 PM

Y by

We first observe that the rearrangement inequality tells us the left-hand side is minimized when $(y_1, \ldots, y_{2020}) = (x_{2020}, x_{2019}, \ldots, x_1)$ , i.e., when the permutation is in reverse order.

Let $a = x_i$ , $b = x_{2021 - i}$ , so each term becomes $((a+1)(b+1))^2.$ The corresponding right-hand side terms are
$4(a^3 + b^3).$ So we want to show: $(a+1)^2(b+1)^2 \ge 4(a^3 + b^3).$
Note that
$4(a^3 + b^3) = 4(a + b)(a^2 - ab + b^2) = 4(a + b)((a - b)^2 + ab).$ On the other hand,
$(a+1)^2(b+1)^2 = (ab + a + b + 1)^2.$ So it suffices to prove: $(ab + a + b + 1)^2 \ge 4(a + b)(ab + 1),$ and this can be checked immediately by AM-GM.

Thus, for the original identity to hold with equality, we must have a-b=1and a+b=1+ab ,this implies b=0 a=1 or b=1 a=2
and then we can assume there are m 0's and 2020-m 1's or n 1's and 2020-n 2's and easily calculate that m=1010.
Hence, the only valid sequences are those where exactly half of the values are 1 and half are 2 (or 0 and 1), arranged such that $x_i + x_{2021 - i}$ is constant across all $i$ .

This post has been edited 2 times. Last edited by math-olympiad-clown, Apr 29, 2025, 2:51 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a