I'm really interested in this problem. After one hour, I have found a solution, but , unfortunately, it was the official one. The inequality is very interesting and deserves attention. I would really like to see another solution.

Can you please post your solution, Harazi? I am very interested in it. Thank you very much.

Let $A$ be the set of those $k$ for which $x_k\le 0$ and $B$ the set of those $k$ for which $x_k>0$. Of course, we can suppose that $A$ has more elements than $B$, which means that $|B|\le\frac{n-1}{2}$. We now re-enumerate $x_1,\ldots ,x_n$ to obtain $y_1\le y_2\le\ldots\le y_n$. We prove that $y_{i+1}-y_i\le 1$ for all $i$. Indeed, let us take $i$. It follows immediately the existence of $k$ such that $y_i$ and $y_{i+1}$ are between $x_k$ and $x_{k+1}$. This means that $y_{i+1}-y_i\le |x_{k+1}-x_k|\le 1$. If $a$ and $b$ are the sums of the negative and positive terms from $y_1,\ldots ,y_n$ then the left side is $|a-b|-|a+b|\le 2|b|$. Thus, it suffices to prove that $b\le\frac{n^2-1}{8}$. But this is easy, since if $y_t$ is the least positive element, then $y_t\le 1$, $y_{t+1}\le 1,\ldots ,y_n\le |B|$ and so $ 0\le b\le 1+2+\ldots +|B|\le\frac{n^2-1}{8}$, since $|B|\le\frac{n-1}{2}$. Very difficult and beautiful problem.

the results of that test are rather contradictory. many people solved the problem, but also many took 0p at it (i was 10th at that time, and I scored a big 0 at this problem. Fortunately for me there were more on the test which I could solve ) ..

This is exactly why I said the problem is very difficult: There aren't many ways of proving it ( I know just one) and you can only take 0 or 7 points. Anyway, the idea is very nice.

manlio wrote: Let $n\ge 1$ be a positive integer and $x_1,x_2\ldots ,x_n$ be real numbers such that $|x_{k+1}-x_k|\le 1$ for $k=1,2,\ldots ,n-1$. Prove that \[\sum_{k=1}^n|x_k|-\left|\sum_{k=1}^nx_k\right|\le\frac{n^2-1}{4}\] Gh. Eckstein What about $n=2$, $x_1=\frac{1}{2}$, $x_2=-\frac{1}{2}$???

Mathuzb wrote: What about $n=2$, $x_1=\frac{1}{2}$, $x_2=-\frac{1}{2}$??? Yeah, so the problem is not true as written and it is also clear where harazi's solution fails: where he w.l.o.g. assumes $\vert B\vert \le \frac{n-1}{2}$. So in fact the argument (and therefore the claim) is correct when $n$ is odd and when $n$ is even we either have $\vert B\vert \le \frac{n-2}{2}$ in which case the same argument yields the upper bound $\frac{n^2-2n}{4}$ or we have $\vert A\vert=\vert B\vert=\frac{n}{2}$ in which case we may assume $y_t \le \frac{1}{2}, y_{t+1} \le \frac{3}{2}, \dotsc$ and hence $b \le \frac{n^2+2n}{8}-\frac{n}{4}=\frac{n^2}{4}>\frac{n^2-2n}{4}$ so that in case where $n$ is even we actually have the (sharp) upper bound $\frac{n^2}{4}$ instead of $\frac{n^2-1}{4}$.

So the problem should be n is odd?