Show that $|x_{k+1}-x_k| \leq 1$ (for $0
Let $n\ge 1$ be a positive integer and let $x_1,\cdots, x_n$ be real numbers so that $|x_{k+1}-x_k|\leq 1$ for $k=1,2,\cdots, n-1$. Show $$\sum_{k=1}^n |x_k| - \left|\sum_{k=1}^n x_k\right|\leq \left\lceil \frac{n^2-1}4\right\rceil.$$
Observe that by replacing $(x_1,\cdots, x_n)$ with $(-x_1,\cdots, -x_n)$, which changes neither the condition that $|x_{k+1}-x_k|\leq 1$ for $1\leq k < n$ nor the inequality to be proven, we can assume there are at most as many positive as negative terms (e.g. one would do such a replacement if this is not the case). So if $P$ denotes the multiset of positive $x_k$'s and $N$ denotes the multiset of negative $x_k$'s, then $|P|\leq (n-1)/2$. Let $(a_1,\cdots, a_n)$ be a permutation of $(x_1,\cdots, x_n)$ in nondecreasing order. Then the elements of $P$ are $a_{k_0+1}\leq a_{k_0+2}\leq \cdots \leq a_{k_0+l}$ for some $l\ge 0$ and some $k_0 > 0$. I think that for any $1\leq i\leq n-1,$ there exist adjacent terms $x_j$ and $x_k$ so that $x_j\leq a_i$ and $x_k\ge a_{i+1}$. So $0\leq a_{i+1}-a_i\leq 1$ by the problem condition.

But how would one prove this?

With the above claim and with notation defined so that $\sigma(P)$ is the sum of the terms in $P$ and $\sigma(N)$ is the sum of the terms in $N$, we then have that the LHS equals $(\sigma(P) - \sigma(N)) - |\sigma(P) + \sigma(N)|.$ But I'm not sure how to simplify this either.
 A: Reorder the $x_i$ such that $x_1 \leq \ldots \leq x_n$. I claim that $|x_i - x_{i+1}| \leq 1$ for any $1 \leq i < n$. Indeed, by assumption we can order the elements from the sequence in such a way that every two consecutive terms are no more than $1$ apart. This means that we cannot have an interval of length at least $1$ with terms on both sides, not containing any terms itself; this proves my claim.
Let $A$ be the average of the $x_i$. We are asked to prove that
$$
\sum_{i=1}^n |x_i| \leq S(n) + n|A|,
$$
where
$$
S(n) = \begin{cases} n^2/4 &\text{if $n$ is even;} \\ (n^2 - 1)/4 &\text{if $n$ is odd.} \end{cases}
$$
First, I claim that the general statement follows from the special case that $A = 0$. Indeed, given any sequence $x_i$ satisfying the conditions from the problem, the sequence $x_1 - A, \ldots x_n - A$ also satisfies the condition from the problem. As such, we obtain by assumption that
$$
\sum_{i = 1}^n |x_i - A| \leq S(n).
$$
Now it follows from the triangle inequality that
$$
\sum_{i=1}^n |x_i| \leq \sum_{i = 1}^n |x_i - A| + n|A|,
$$
proving our claim. Thus we may assume that $A = 0$. Let $1 < t < n$ be such that $x_t \leq 0 \leq x_{t+1}$. As the problem dictates, we must make a case distinction.
Suppose first that $n = 2k+1$ is odd. By replacing the sequence by its negative, we may assume that $t \leq k$. Starting from $0 \leq x_{t+1}$, by iterating my claim at the start of the proof, it follows that $x_i \geq - (t+1-i)$ for any $i \leq t$. Because we assume that $A = 0$, it follows that
$$
\sum_{i=1}^t |x_i| = \sum_{i=t+1}^n |x_i|.
$$
We may then estimate that
$$
\sum_{i=1}^n |x_i| = 2\sum_{i=1}^t |x_i| \leq 2 \sum_{i=1}^t t+1-i = t(t+1) \leq k(k+1) = S(n).
$$
Now suppose that $n = 2k$ is even. If $t < k$, the above argument can be copied verbatim, using that in that case,
$$
\sum_{i=1}^n |x_i| \leq t(t+1) \leq k(k-1) < S(n).
$$
If $t = k$, more care is required. I claim that in that case, either $x_t$ or $x_{t+1}$ must be contained in the interval $[-1/2,1/2]$. Indeed, this follows directly from my claim at the start of the proof. Therefore, by replacing the sequence by its negative if necessary, we may assume that $x_t \geq -1/2$. Then we may more carefully estimate that $x_i \geq -(t + 1/2 - i)$ for any $i \leq t$. The same computation as before then yields that
$$
\sum_{i=1}^n |x_i| \leq k^2 = \frac{n^2}{4}.
$$
