# Inequality, Vojtěch Jarník Competition 2006

This is the problem from Vojtěch Jarník Competition 2006. Given real numbers $0=x_1,x_2<\dots<x_{2n}<x_{2n+1}=1$ such that $x_{i+1}-x_{i}\leq h$ for $1\leq i \leq 2n$, show that $$\frac{1-h}{2}<\sum^n_{i=1}x_{2i}(x_{2i+1}-x_{2i-1})<\frac{1+h}{2}$$ So far I have achieved some results, but couldn't proceed any further: $$\sum^n_{i=1}x_{2i}(x_{2i+1}-x_{2i-1})=x_2(x_3-x_1)+x_4(x_5-x_3)+x_6(x_7-x_5)+\dots=x_3(x_2-x_4)+x_5(x_4-x_6)+\dots$$

$$x_{i+1}-x_{i}\leq h$$ $$x_{i}-x_{i-1}\leq h$$ $$\dots$$ $$\frac{x_{i+1}-x_{i-m}}{m+1}\leq h$$

$$x_{2i-1}>\frac{x_{2i-1}+x_{2i-2}}{2}>x_{2i-1}x_{2i-2}>x_{2i-2}$$ $$x_{2i}>\frac{x_{2i}+x_{2i-1}}{2}>x_{2i}x_{2i-1}>x_{2i-1}$$ $$x_{2i-1}-x_{2i}>\frac{x_{2i-2}-x_{2i}}{2}>x_{2i-1}(x_{2i-2}-x_{2i})>x_{2i-2}-x_{2i-1}\geq -h$$

$$\frac{1+h}{2}\geq \frac{x_i-x_{i-n}+n}{2n}=\dfrac{\dfrac{x_i-x_{i-n}}{n}+1}{2}>\frac{x_i-x_{i-n}}{n}$$ I would not mind to see not only hints but full proofs as well, in case I am nowhere near the truth

-
Competition questions are best solved by oneself! That's the only way to get better in solving them. As they say, practice makes perfect. For this particular question, the trick is to convert the "difference sequence" presentation to "partial summation", which is more useful here. – Yuval Filmus Feb 18 '12 at 2:47

Let $p_i = x_{2i+1} - x_{2i-1}$. Note that $$\sum_{i=1}^n p_i = 1.$$ Denote $a_i = x_{2i} - x_{2i-1}$, $b_i = x_{2i+1} - x_{2i}$. We have $$x_{2i} = \sum_{j < i} p_j + a_i.$$ Now $a_i + b_i = p_i$ and $0 \leq a_i,b_i \leq h$. Hence $$|a_i - p_i/2| = |(b_i-a_i)/2| \leq h/2.$$ Define $a_i = p_i/2 + \delta_i$, so $|\delta_i| \leq h/2$ and $$x_{2i} = \sum_{j < i} p_j + p_i/2 + \delta_i.$$ Now we're in good shape since \begin{align*} \sum_{i=1}^n x_{2i} (x_{2i+1} - x_{2i-1}) &= \sum_{i=1}^n \sum_{j<i} p_i p_j + \frac{1}{2} \sum_{i=1}^n p_i^2 + \sum_{i=1}^n \delta_i p_i \\ &= \frac{1}{2}\left(\sum_{i=1}^n p_i\right)^2 + \sum_{i=1}^n \delta_i p_i \\ &= \frac{1}{2} + \sum_{i=1}^n \delta_i p_i. \end{align*} Since $\sum_{i=1}^n p_i = 1$ and $|\delta_i| \leq h/2$, we deduce $$\left|\sum_{i=1}^n x_{2i} (x_{2i+1} - x_{2i-1}) - \frac{1}{2}\right| \leq \frac{h}{2}.$$
The sum in question is a Riemann sum approximating $\int_0^1x\,dx$. But you don't need to know that. Draw a picture and you see the sum is the area of a bunch of rectangles.
The area of the rectangles equals $T + P - N$, where $T=1/2$ is the area of the triangle with vertices $(0,0)$, $(1,0)$ and $(1,1)$, $P$ is the green area, and $N$ is the red area. Each of the red triangles is confined to its own parallelogram (from $x_{2i-1}$ to $x_{2i+1}$, with height $h$) so the total red area is at most $h/2$. Similarly the green area is at most $h/2$. The result follows from $T-N\le T+P-N\le T+P$.