Maths Olympiad Prep

Library / /13 of 43

Algebra Difficulty 5.5 AIME, harder Prove it JBMO

Problem:
Let x1,x2,…,xnx_{1}, x_{2}, \ldots, x_{n} be real numbers satisfying ∑k=1n−1min⁡(xk,xk+1)=min⁡(x1,xn)\sum_{k=1}^{n-1} \min \left(x_{k}, x_{k+1}\right)=\min \left(x_{1}, x_{n}\right).
Prove that ∑k=2n−1xk≥0\sum_{k=2}^{n-1} x_{k} \geq 0.

Solution

Solution:
Case I. If min⁡(x1,xn)=x1\min \left(x_{1}, x_{n}\right)=x_{1}, we know that xk≥min⁡(xk,xk+1)x_{k} \geq \min \left(x_{k}, x_{k+1}\right) for all k∈{1,2,3,…,n−1}k \in\{1,2,3, \ldots, n-1\}. So x1+x2+…+xn−1≥∑k=1n−1min⁡(xk,xk+1)=min⁡(x1,xn)=x1x_{1}+x_{2}+\ldots+x_{n-1} \geq \sum_{k=1}^{n-1} \min \left(x_{k}, x_{k+1}\right)=\min \left(x_{1}, x_{n}\right)=x_{1}, hence ∑k=2n−1xk≥0\sum_{k=2}^{n-1} x_{k} \geq 0.

Case II. If min⁡(x1,xn)=xn\min \left(x_{1}, x_{n}\right)=x_{n}, we know that xk≥min⁡(xk−1,xk)x_{k} \geq \min \left(x_{k-1}, x_{k}\right) for all k∈{2,3,4,…,n}k \in\{2,3,4, \ldots, n\}. So x2+x3+…+xn≥∑k=1n−1min⁡(xk,xk+1)=min⁡(x1,xn)=xnx_{2}+x_{3}+\ldots+x_{n} \geq \sum_{k=1}^{n-1} \min \left(x_{k}, x_{k+1}\right)=\min \left(x_{1}, x_{n}\right)=x_{n}, hence ∑k=2n−1xk≥0\sum_{k=2}^{n-1} x_{k} \geq 0.

Since min⁡(a,b)=12(a+b−∣a−b∣)\min (a, b)=\frac{1}{2}(a+b-|a-b|), after substitutions, we will have:
∑k=1n−112(xk+xk+1−∣xk−xk+1∣)=12(x1+xn−∣x1−xn∣)⇔…2(x2+x3+…+xn−1)+∣x1−xn∣=∣x1−x2∣+∣x2−x3∣+…+∣xn−1−xn∣ \begin{aligned} \sum_{k=1}^{n-1} \frac{1}{2}\left(x_{k}+x_{k+1}-\left|x_{k}-x_{k+1}\right|\right) &=\frac{1}{2}\left(x_{1}+x_{n}-\left|x_{1}-x_{n}\right|\right) \\ &\Leftrightarrow \ldots \\ 2\left(x_{2}+x_{3}+\ldots+x_{n-1}\right)+\left|x_{1}-x_{n}\right| &=\left|x_{1}-x_{2}\right|+\left|x_{2}-x_{3}\right|+\ldots+\left|x_{n-1}-x_{n}\right| \end{aligned}
As ∣x1−x2∣+∣x2−x3∣+…+∣xn−1−xn∣≥∣x1−x2+x2−x3+…+xn−1−xn∣=∣x1−xn∣\left|x_{1}-x_{2}\right|+\left|x_{2}-x_{3}\right|+\ldots+\left|x_{n-1}-x_{n}\right| \geq\left|x_{1}-x_{2}+x_{2}-x_{3}+\ldots+x_{n-1}-x_{n}\right|=\left|x_{1}-x_{n}\right|, we obtain the desired result.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.