Given a positive integer $n$ and $x_1 \leq x_2 \leq \ldots \leq x_n, y_1 \geq y_2 \geq \ldots \geq y_n$, satisfying \[\displaystyle\sum_{i = 1}^{n} ix_i = \displaystyle\sum_{i = 1}^{n} iy_i\] Show that for any real number $\alpha$, we have \[\displaystyle\sum_{i =1}^{n} x_i[i\alpha] \geq \displaystyle\sum_{i =1}^{n} y_i[i\alpha]\] Here $[\beta]$ denotes the greastest integer not larger than $\beta$.
Problem
Source:
Tags: inequalities, algebra unsolved, algebra
02.12.2014 12:41
First, note that following 2 inequalities: $\frac{k-1}{2}[k\alpha]\geq [\alpha]+[2\alpha]+...+[(k-1)\alpha]$ and $\frac{c(c+1)}{2}x_c+(c+1)x_{c+1}+...+nx_{n}\geq \frac{c(c+1)}{2}y_c+(c+1)y_{c+1}+...+ny_{n}$ for all $1\leq c\leq n$. From $1$ and $2$, we deduce that $([c\alpha]-\frac{2}{c-1}([\alpha]+...+[(c-1)\alpha]))x_c+\frac{2(c+1)}{c(c+1)}([c\alpha]-\frac{2}{c-1}([\alpha]+...+[(c-1)\alpha]))x_{c+1}+...+\frac{2n}{c(c+1)}([c\alpha]-\frac{2}{c-1}([\alpha]+...+[(c-1)\alpha]))x_n\geq ([c\alpha]-\frac{2}{c-1}([\alpha]+...+[(c-1)\alpha]))y_c+\frac{2(c+1)}{c(c+1)}([c\alpha]-\frac{2}{c-1}([\alpha]+...+[(c-1)\alpha]))y_{c+1}+...+\frac{2n}{c(c+1)}([c\alpha]-\frac{2}{c-1}([\alpha]+...+[(c-1)\alpha]))y_n$ Summing this from $1\leq c\leq n$, we get for each $x_i$ the coefficient: Sum of $\frac{2i}{c(c+1)}([c\alpha]-\frac{2}{c-1}([\alpha]+...+[(c-1)\alpha]))x_{i}$ from $1\leq c\leq i-1$ and $([i\alpha]-\frac{2}{i-1}([\alpha]+...+[(i-1)\alpha]))x_i$ wehn $c=i$. the coefficient of $[i\alpha]$ is clearly $1$, whereas for $[k\alpha]$, it is $\frac{2i}{k(k+1)}-\frac{2}{i-1}-\frac{4i}{k(k+1)(k+2)}-...-\frac{4i}{(i-2)(i-1)i}=0$, and hence $[\alpha]x_1+...+[n\alpha]x_n\geq [\alpha]y_1+...+[n\alpha]y_n$
22.12.2017 17:48
We can also prove by induction on $n\in \mathbb{Z}^+$. The base case is obvious. For inductive step, suppose the problem is true when $n\leftarrow m$ where $m\in \mathbb{Z}^+$, we'll prove that it's true when $n\leftarrow m+1$. Say we've $x_1\leq x_2\leq ...\leq x_{m+1}$ and $y_1\geq y_2\geq ...\geq y_{m+1}$ satisfying $\sum_{i=1}^{m+1}{ix_i} =\sum_{i=1}^{m+1}{iy_i}$. Setting new variables $a_i=x_i+\frac{2x_{m+1}}{m}$ and $b_i=y_i+\frac{2y_{m+1}}{m}$ for all positive integer $i\leq m$. It's easy to see that $a_1\leq a_2\leq ...\leq a_m$ and $b_1\geq b_2\geq ...\geq b_m$ satisfying $\sum_{i=1}^{m}{ia_i} =\sum_{i=1}^{m}{ib_i}$. By induction hypothesis, for any real number $\alpha$, we've $\sum_{i=1}^{m}{a_i\lfloor i\alpha\rfloor }\geq \sum_{i=1}^{m}{b_i\lfloor i\alpha \rfloor }$. We want to show that $\sum_{i=1}^{m+1}{x_i\lfloor i\alpha\rfloor } -\sum_{i=1}^{m}{a_i\lfloor i\alpha\rfloor } \geq \sum_{i=1}^{m+1}{y_i\lfloor i\alpha\rfloor } -\sum_{i=1}^{m}{b_i\lfloor i\alpha\rfloor }$. This simplified to $x_{m+1}\times \Big( \lfloor (m+1)\alpha \rfloor-\sum_{i=1}^{m}{\frac{2\lfloor i\alpha \rfloor }{m}}\Big) \geq y_{m+1}\times \Big( \lfloor (m+1)\alpha \rfloor-\sum_{i=1}^{m}{\frac{2\lfloor i\alpha \rfloor }{m}}\Big) $. Note that if $x_{m+1}<y_{m+1}$, we get that $x_1\leq x_2\leq ...\leq x_{m+1}< y_{m+1}\leq y_m\leq ...\leq y_1$, which is impossible to get the condition $\sum_{i=1}^{m+1}{ix_i} =\sum_{i=1}^{m+1}{iy_i}$. So, $x_{m+1}\geq y_{m+1}$. The rest is to show that $\lfloor (m+1)\alpha \rfloor-\sum_{i=1}^{m}{\frac{2\lfloor i\alpha \rfloor }{m}} =\frac{m\lfloor (m+1)\alpha \rfloor-\sum_{i=1}^{m}{2\lfloor i\alpha \rfloor }}{m} \geq 0$. The last inequality is true by summing $\lfloor (m+1)\alpha \rfloor \geq \lfloor i\alpha \rfloor +\lfloor (m+1-i)\alpha \rfloor$ for all $i\in \{ 1,2,...,m\}$.