Suppose otherwise. If $x_i<x_{i+1}$, from $x_i^2+x_{i+1}^2> 2x_{i+1}x_{i+2}$, we infer $x_{i+1}>x_{i+2}$. If $x_i>x_{i+1}$, from $x_i^2+x_{i+1}^2>2x_ix_{i-1}$ we infer $x_i>x_{i-1}$. This implies that the signs between consecutive $x_i$s have to alternate which combined with the parity of $n$ yields either $x_n<x_1<x_2$ or $x_n>x_1>x_2$, both of which are impossible by the previous observations.

trungnghia215 wrote: Since $n$ is odd integer, we get $n \ge 3$. WLOG, assume $x_{1} \le x_{2} \le \cdots \le x_{n}$. We need to show that $x_{1}^{2} + x_{2}^{2}\le 2x_{n - 1}x_{n}$. For contrary, suppose $x_{1}^{2} + x_{2}^{2} > 2x_{n - 1}x_{n} \ge 2x_{n - 1}^{2} \ge 2x_{2}^{2} \implies x_{1}^{2} > x_{2}^{2}$ which is a contradition. Is it right? You can't assume WLOG $x_1 \le x_2 \le ... \le x_n$ (I think)

It suffices to exhibit a single value of $i$, $j$ such that $x_i^2 + x_{i+1}^2 \le 2 x_j x_{j+1}$. Since $n$ is odd we can find three adjacent $x_k$'s, call them $a$, $b$, $c$ (with $b$ in middle) such that $a \ge b \ge c$. Then $2ab \ge b^2+c^2$ so done.

Assume the contrary, then we have $x_i^2 + x_{i+1}^2 > 2x_jx_{j+1} \forall i,j\le n$. There must be two different numbers, as other wise the problem is trivial. Now WLOG let $x_1 < x_2$, then $2x_2^2 > x_1^2 + x_2^2 > 2x_2x_3 \implies x_2 > x_3$. Now we'll prove that $x_{i-1} < x_i > x_{i+1}$ for every even integer $i\le n$ using induction. We already proved the base case, so now let's assume that it holds for some even integer $k$. Assume that $x_{k+1} \ge x_{k+2}$, then: $$2x_{k+1}^2 \ge x_{k+1}^2 + x_{k+2}^2 > 2x_{k+1}x_k \implies x_{k+1} > x_{k} \quad \quad \text{Contradiction.}$$ Now: $$2x_{k+2}^2 \ge x_{k+1}^2 + x_{k+2}^2 > 2x_{k+2}x_{k+3} \implies x_{k+2} > x_{k+3}$$ Hence the claim is proven. Now assume that $x_n \ge x_1$. Then: $$2x_n^2 \ge x_n^2 + x_1^2 > 2x_nx_{n-1} \implies x_n > x_{n-1}$$ Contradiction, as $n$ is an odd integer. Now assume that $x_n \le x_1$. Then: $$2x_1^2 \ge x_n^2 + x_1^2 > 2x_1x_2 \implies x_1 > x_2$$ Contradiction. Because neither $x_n \ge x_1$, not $x_n \le x_1$ we obtain the wanted contradiction. Q.E.D.

Can someone please explain this ( trivial ? ) observation --- Quote: Since $n$ is odd we can find three adjacent $x_k$'s, call them $a$, $b$, $c$ (with $b$ in middle) such that $a \ge b \ge c$. Then $2ab \ge b^2+c^2$ so done. Thanks in advance !

PRO2000 wrote: Can someone please explain this ( trivial ? ) observation --- Quote: Since $n$ is odd we can find three adjacent $x_k$'s, call them $a$, $b$, $c$ (with $b$ in middle) such that $a \ge b \ge c$. Then $2ab \ge b^2+c^2$ so done. Thanks in advance ! $2ab=ab+ab \ge b^2+c^2$ since $a \ge b \ge c$.

I asked abt. why we can find such $a,b,c$

PRO2000 wrote: I asked abt. why we can find such $a,b,c$ If there doesn't exist such a triplet, then the numbers must alternate between higher than the previous number and lower than the previous number. However, since $n$ is odd the parity doesn't work out.

If you have seen 2011China national math Olympiad -question 1, ha!

IstekOlympiadTeam wrote: Let $n$ be an odd positive integer, and let $x_1,x_2,\cdots ,x_n$ be non-negative real numbers. Show that \[ \min_{i=1,\ldots,n} (x_i^2+x_{i+1}^2) \leq \min_{j=1,\ldots,n} (2x_jx_{j+1}) \]where $x_{n+1}=x_1$. When $n=3$, take $x_1=0$, $x_2=x_3=1$, we have $LHS=1$ while $RHS=0$. I think in RHS $\min$ should be replaced by $\max$.

izzystar wrote: IstekOlympiadTeam wrote: Let $n$ be an odd positive integer, and let $x_1,x_2,\cdots ,x_n$ be non-negative real numbers. Show that \[ \min_{i=1,\ldots,n} (x_i^2+x_{i+1}^2) \leq \min_{j=1,\ldots,n} (2x_jx_{j+1}) \]where $x_{n+1}=x_1$. When $n=3$, take $x_1=0$, $x_2=x_3=1$, we have $LHS=1$ while $RHS=0$. I think in RHS $\min$ should be replaced by $\max$. I remember yesterday ... It was max ....

Suppose the contrary. First I wondered why must $n$ is odd, then immediately i got the following counter example for $n$ even: $x_{2i}=a, x_{2i+1}=b$ and $a\neq b$. So this means that $n$ is odd must be very important, so i played around some parity things on $n$, in particular on the ordering of $x_1, x_2, \cdots x_n$. My strategy is to look at specific pairs of $(i, j)$ that will be able to solve the problem. So for $n$ odd you can't have 'alternating' ordering. This motivates to look at triplets $(x_i, x_{i+1}, x_{i+2})$. The crucial inequality is $2xy\ge y^2+z^2$ for $x\ge y\ge z$. Since $n$ is odd, there must exist some $k$ with $x_k\ge x_{k+1}\ge x_{k+2}$ or $x_k\le x_{k+1}\le x_{k+2}$. However then we can take $i=k+1, j=k$ and $i=k, j=k+1$ respectively. then $x_i^2+x_{i+1}^2\ge 2x_jx_{j+1}$ for that choice of $i, j$, contradiction. This solves the problem.

Say that $x_i$ neighbors $x_{i-1}$ and $x_{i+1}$. Then if $X$ is the $(k+1)$-th largest $x_i$ (where $n=2k+1$), then exactly $k$ of the $x_i$ are smaller than $X$, and $k$ are larger. If we delete $k$ of the $x_i$, some neighboring pair must remain. It follows that we may select two neighboring $x_i$'s, both of which are $\le X$, and two which are $\ge X$. If we call the former $x_k,x_{k+1}$ and the latter $x_j,x_{j+1}$, then \[ \min_{i=1,\ldots,n} (x_i^2+x_{i+1}^2) \le x_k^2+x_{k+1}^2\le 2X^2\le 2x_jx_{j+1}\le \max_{j=1,\ldots,n} (2x_jx_{j+1}). \]

Suppose that the given inequality is not true. Let $M=\max_{j=1,\ldots,n} (2x_jx_{j+1})$, $m=\sqrt{\frac{M}{2}}$ and $A=min_{i=1,\ldots,n} (x_i^2+x_{i+1}^2)$ If $x_k=m$ for some $k$, then: If $x_{k+1}<m$, $A \leq x_k^2+x_{k+1}^2<2m^2=M$, contradiction. If $x_{k+1}>m$, $2x_kx_{k+1}>2m^2=M$, contradicting the definition of $M$. Therefore $x_{k+1}=m$. But this gives: $A \leq x_k^2+x_{k+1}^2=2m^2=M$, contradiction. If $x_k<m$ for some $k$, then: If $x_{k+1}<m$, $A \leq x_k^2+x_{k+1}^2<2m^2=M$, contradiction. Therefore $x_{k+1}>m$. If $x_k>m$ for some $k$, then: If $x_{k+1}>m$, $2x_kx_{k+1}>2m^2=M$, contradicting the definition of $M$. Therefore $x_{k}<m$. Therefore the sequence $x_1,x_2,\cdots ,x_n$ alternates between being greater and smaller than $m$. Wlog $x_1$ smaller than $m$. Then $x_2$ greater than $m$ etc and since $n$ odd, $x_n$ smaller than $m$ implying that $x_1$ is greater than $m$, contradiction. Therefore the given inequality is true.

Quote: Since $n$ is odd we can find three adjacent $x_k$'s, call them $a$, $b$, $c$ (with $b$ in middle) such that $a \ge b \ge c$. Then $2ab \ge b^2+c^2$ so done. How would this work with x1=23, x2=30, x3=20, x4=25, x5=22?

v_Enhance wrote: It suffices to exhibit a single value of $i$, $j$ such that $x_i^2 + x_{i+1}^2 \le 2 x_j x_{j+1}$. Since $n$ is odd we can find three adjacent $x_k$'s, call them $a$, $b$, $c$ (with $b$ in middle) such that $a \ge b \ge c$. Then $2ab \ge b^2+c^2$ so done. I really don't understand why such a triple exists. Could you please elaborate ? Thank you. Edit: Never mind, I just realised $n $ is odd.

Consider the value $(x_i-x_{i+1})(x_{i+1}-x_{i+2})$. If this is positive, either $x_i \ge x_{i+1} \ge x_{i+2}$ or $x_i \le x_{i+1} \le x_{i+2}$. This gives us $x^2_{i+1}+x^2_{i+2} \le 2x_ix_{i+1}$ or $x^2_i + x^2_{i+1} \le 2x_{i+1}x_{i+2}$, so we are done. Assume that $(x_i-x_{i+1})(x_{i+1}-x_{i+2})<0$ for all $i$. Multiplying this for $i=1,2, \cdots n$ gives us an immediate contradiction, since $\prod_{i=1}^n (x_i-x_{i+1})^2$ cannot be negative.

extremely silly solution time Notice that any alternating sequence $a$, $b$, $a$, $b$, ... $a$ satisfies the inequality. For shorthand let "minimum" denote $\min (x_i^2 + x_{i+1}^2)$ and "maximum" denote $\max (2x_jx_{j+1})$. Pick $x_i$ such that $x_i^2 + x_{i+1}^2$ is minimal, and pick $x_j$ such that $x_jx_{j+1}$ is maximal. Call a member of the sequence $nice$ if and only if it is either $x_i$, $x_{i+1}$, or replaced by $x_i$ or $x_{i+1}$. Define a $move$ as replacing a non-nice number $x_{a\pm 2}$ with a nice number $x_a$. Now, if $x_j \ge x_i$ or $x_j \ge x_{i+1}$, there exists some sequence of moves such that the smaller of the two replaces $x_j$, due to $n$ being odd. This never increases the maximal product. Continuing all the way results in a sequence in an alternating form, which always works. The minimum is the same and the maximum hasn't increased, as desired. Suppose on the contrary $x_j < x_i, x_{i+1}$. Then by similar reasoning $x_{j+1} < x_i, x_{i+1}$. But this contradicts the minimality of $x_i^2 + x_{i+1}^2$, so done.

Kind of an oddball problem. Assume for the sake of contradiction that $x_i^2+x_{i+1}^2 \geq 2x_jx_{j+1}$ for any pair of indices $(i, j)$. Without loss of generality, let $x_1 \leq x_2$ (as otherwise just relabel backwards). Then, observe that $$2x_1x_2 \leq x_2^2+x_3^2 \implies x_1 \leq \frac{x_2^2+x_3^2}{2x_2} = \frac 12 \left(x_2+\frac{x_3^2}{x_2}\right),$$which implies that $x_1 \leq x_3$; this implies $x_2 \leq x_3$ too. As a result, $$2x_3x_4 \leq x_2^2+x_3^2 \implies x_4 \leq \frac 12 \left(x_3 + \frac{x_2^2}{x_3}\right)$$means $x_4 \leq x_3$. So now, apply the same argument with the same indices shifted by $2$ (as $x_4 \leq x_3$ holds), which yields the conclusion $x_3 \leq x_5$. Continuing in a similar fashion, using the fact that $n$ is odd, we have the inequality chain $$x_1 \leq x_3 \leq x_5 \leq \cdots \leq x_2 \leq x_4 \leq \cdots,$$where every term is included in the inequality chain. Obviously by cyclicity, this implies that all the $x_i$ are equal, which is a contradiction.

Bruh this looks wrong now cuz all the other solutions look so much more complicated :sob: WLOG, assume that $\min(x_i^2+x_{i+1}^2)=x_1^2+x_2^2$. Notice that in order to prove the claim, we do not have to prove that it is less than exactly the maximum, we just need to prove that there exists some $j$ such that $x_1^2+x_2^2\leq{}2x_jx_{j+1}$. Notice that $x_1^2+x_2^2\leq{}x_2^2+x_3^2$, giving us that $x_3\geq{}x_1$. Therefore, if $x_1\geq{}x_2$, then we have that $x_3\geq{}x_1\geq{}x_2$, giving us that $x_2^2\leq{}x_2x_3$, and $x_1^2\leq{}x_2x_3$, proving that $x_1^2+x_2^2\leq{}2x_2x_3$. Similarly, if $x_1\leq{}x_2$, then we have that $x_1^2+x_2^2\leq{}2x_2x_n$, both of which imply that $\min(x_i^2+x_{i+1}^2) \le \max(2x_jx_{j+1})$, and we are done.

We uploaded our solution https://calimath.org/pdf/EGMO2016-1.pdf on youtube https://youtu.be/qyWZ2KgwBek.

Nice problem! Suppose otherwise, implying that any $x_i^2+x_{i+1}^2>2x_jx_{j+1}$, since even the extremal case holds. $$\forall x_i<x_{i+1}\implies 2x_{i+1}^2>x_i^2+x_{i+1}^2>2x_{i+1}x_{i+2}\implies x_{i+1}>x_{i+2}$$$$\forall x_j>x_{j+1}\implies 2x_j^2>x_j^2+x_{j+1}^2>2x_jx_{j-1}\implies x_j>x_{j-1},$$so that either $$x_k<x_{k+1}\implies x_k<x_{k+1}>x_{k+2}\text{ or }x_k>x_{k+1}\implies x_{k-1}<x_k>x_{k+1},$$which have the same result, implying this holds regardless of the pairwise consecutive relationships. But due to n=2l+1, if WLOG $x_{2m+1}<x_{2m+2}>x_{2m+3}\implies\dots x_{2l+1}<x_1<x_2$, which is a direct and an evident contradiction. $\blacksquare$

Assume ftsoc that for all $1 \le i, j \le n$ we have $x_i^2 + x_{i + 1}^2 > 2x_jx_{j + 1}$. Note that this implies no two consecutive $x_i$ are equal. So, we may cycle the terms such that $x_1 > x_2$ (the proof when $x_1 < x_2$ is basically the same anyways). Then from $x_2^2 + x_3^2 > 2x_1x_2 > 2x_2^2$, we find that $x_2 < x_3$. Also, from $2x_3^2 > x_2^2 + x_3^2 > 2x_3x_4,$ we have $x_3 > x_4$. Continuing in this manner, because $n$ is odd, we find that $x_4 < x_5 > x_6 < \cdots > x_{n - 1} < x_n > x_1 < x_2$, contradiction.

FTSOC assume otherwise; we must have $x_i^2+x_{i+1}^2 > 2x_jx_{j+1}$ as the extremal case holds. If $x_i<x_{i+1}$, we have \[2x_{i+1}^2>x_i^2+x_{i+1}^2 > 2x_{i+1}x_{i+2} \implies x_{i+1}>x_{i+2}.\] If $x_i>x_{i+1}$, we have \[2x_{i}^2>x_i^2+x_{i+1}^2 > 2x_{i-1}x_{i} \implies x_{i}>x_{i-1}.\] Hence, the sequence will always alternate from greater or less than, but since we have an odd number of terms, this will result in either \[ x_n<x_{n+1} = x_1<x_2 \ \text{ or } \ x_n> x_{n+1} = x_1>x_2,\] both of which are contradictions. $\square$

Solved with dolphinday. We wasted so much time without making the right observation bruh. Since $n$ is odd, we have three consecutive indices $a,b,c$ such that $a\geq b\geq c$. To see why, assume that signs always alternate between consecutive terms. Then, we have \[x_1 \geq x_2 \leq x_3 \geq x_4 \leq \dots \leq x_n \geq x_1\]But this immediately means that $x_n \geq x_1 \geq x_2$ which is what was desired. Now that we have such $a,b,c$ simply note that, \[\min(x_i^2+{x_{i+1}^2}) \leq b^2 + c^2 \leq 2ab \leq \max(2x_ix_{i+1})\]as desired.

Onk. Assume otherwise. Note that no two elements may be equal, and that it suffices to show that as some point we can find some \[x_ix_{i+1} \geq x_j^2 + x_{j+1}^2\]not necessarily the maximum or minimum as in the problem statement, as we are then showing a stronger inequality. Claim: The sequence alternates increasing and decreasing. For example $4 3 5 2 7$, in which $4 > 3$, $3 < 5$, $ 5 > 2$, and $2 < 7$. Proof. Consider three consecutive numbers $x$, $y$, and $z$. Then clearly we must have, \begin{align*} x^2 + y^2 &> 2yz\\ y^2 + z^2 &> 2xy \end{align*}Assume now that $x > y$. Then from the second equation we find, \begin{align*} y^2 + z^2 &> 2y^2\\ \iff z &> y \end{align*}Otherwise assume that $x < y$. Then we find from the first equation that, \begin{align*} 2y^2 &> 2yz\\ \iff y &> z \end{align*}This proves the claim. $\square$ Now as $n$ is odd, we may easily see that if we begin from anywhere in the loop, and start alternating and decreasing terms we find a contradiction. Namely we find three consecutive terms $x$, $y$ and $z$ satisfying $x > y > z$ or $x < y < z$. For example in our ``test" sequence of $43527$ we may see that $7 > 4 > 3$. Thus we are done. $\blacksquare$

The condition that $n$ is odd implies the existence of three consecutive terms in either weakly ascending or weakly descending order. WLOG suppose these three terms are $x_1 \ge x_2 \ge x_3$. We get the desired by noting that \[\max(2x_jx_{j+1}) \ge 2x_1x_2 \ge x_2^2 + x_2^2 \ge x_2^2 + x_3^2 \ge \min(x_i^2+x_{i+1}^2). \quad \blacksquare\]

<A1 for sure as I can't even solve A1 Lemma: if $a\geq b\geq c$ then $2ab\geq b^2+c^2$ Proof:$$c^2\leq ab\leq b(2a-b)=2ab-b^2$$and similarly we have $a\leq b\leq c$ then $2bc\geq a^2+b^2$. With $n$ odd we're done as there always exists $i$ such that $x_i, x_{i+1}, x_{i+2}$ are increasing or decreasing.

Isn't this so easy

Assume otherwise. Note that $x_i \ge x_{i+1} \ge x_{i+2}$ and $x_i \le x_{i+1} \le x_{i+2}$ both give contradictions. So the sign of $x_{i+1} - x_i$ must alternate. But since $n$ is odd, this is impossible.