Showing $x_n-x_nx_1+\sum_{k=1}^{n-1} (x_k-x_kx_{k+1})\leq\left\lfloor\frac{n}{2}\right\rfloor$, with $x_i\in[0,1]$

contest-mathinequalitysequences-and-series

Let $x_1, x_2,\ldots, x_n$ be arbitrary numbers from the interval $[0,1]$ with $n>1$.
Show that $$x_n-x_nx_1+\sum_{k=1}^{n-1} (x_k-x_kx_{k+1})\leq\left\lfloor\frac{n}{2}\right\rfloor$$

I tried to factor out the $x_k$ from each term to show that if the coefficient $x_k$ of $x_k(1-x_{k+1})$ is larger than $\dfrac{1}{2}$, then the term $x_{k-1}(1-x_k)$ must be smaller than $\dfrac12$, but I don't know where to go from here or if it is even the right approach.

Best Answer

Use $\mod n$ for subscripts and call the expression you want to maximize $X$.

If $2\mid n$, by simple transformation, \begin{align*}X={}&\sum_{k=1}^n\left(\frac{a_k}2-a_ka_{k+1}+\frac{a_{k+1}}2\right)\\[2pt]={}&\sum_{k=1}^n\left(-\frac{\left(2a_k-1\right)\left(2a_{k+1}-1\right)-1}4\right).\end{align*} Since $2a_k-1$ and $2a_{k+1}-1\in[-1,1]$, each term of the sum $\le\dfrac12$. So $X\le\dfrac n2=\left\lfloor\dfrac n2\right\rfloor$.

If $2\nmid n$, notice that $X$ is a linear function of $a_n$, so maximum is reached at $a_n=0$ or $1$. If $a_n=0$, also $a_1a_n=0$, then \begin{align*}X={}&\sum_{k=1}^{(n-1)/2}\left(a_{2k-1}+a_{2k}-a_{2k-1}a_{2k}-a_{2k}a_{2k+1}\right)\\[2pt]\le{}&\sum_{k=1}^{(n-1)/2}\left(a_{2k-1}+a_{2k}-a_{2k-1}a_{2k}\right)\\[2pt]={}&\sum_{k=1}^{(n-1)/2}\left(1-(1-a_{2k})(1-a_{2k-1})\right)\\[2pt]\le{}&1\cdot\frac{n-1}2=\frac{n-1}2=\left\lfloor\frac n2\right\rfloor.\end{align*} If $a_n=1$, then $a_1a_n$ cancels with $a_1$. So \begin{align*}X={}&\sum_{k=1}^{(n-1)/2}\left(a_{2k}+a_{2k+1}-a_{2k-1}a_{2k}-a_{2k}a_{2k+1}\right)\\[2pt]\le{}&\frac{n-1}2=\left\lfloor\frac n2\right\rfloor.\end{align*} This inequality can be proved by a nearly identical method with the one demonstrated in the last case.

Related Question