Minimizing absolute differences between n values under constraints on sums of these values I have 15 unknown integer values $x_i$. I know that: $$\sum_{i=1}^5 x_i = 25 $$, $$\sum_{i=6}^{10} x_i = 32 $$ and $$\sum_{i=11}^{15} x_i = 41 $$
I wish to identify 15 integer $x_i$ that minimize $$\sum_{i=1}^{14} |x_{i+1} - x_i|$$ under these constraints. Is it possible? How should I proceed?
Thank you very much for your help
 A: We can show that $\sum_{i=1}^{14}|x_{i+1}-x_i|\geq |x_k-x_j|$ for any $j,k.$ It is trivially true if $j=k$. If $j<k$ then:
$$\sum_{i=1}^{14} |x_{i+1}-x_i|\geq\sum_{i=j}^{k-1} |x_{i+1}-x_i|\geq \left|\sum_{i=j}^{k-1} x_{i+1}-x_i\right|=|x_k-x_j|$$
If $j>k$ just reverse them.
Now, one of $x_{11},\dots,x_{15}$ must be at least $9$. And one of $x_{1},\dots,x_{5}$ must be at most $5$. So the we get that:
$$\sum_{i=1}^{14}|x_{i+1}-x_i|\geq 4.$$
We can easily reach this minimum with $$(x_i)=(5,5,5,5,5,\quad6,6,6,7,7,\quad,8,8,8,8,9).$$
There's a more general rule than the above:

Lemma: If $(x_i)_{i=1}^{N}$ is a sequence then:
  $$\sum_{i=1}^{N-1} |x_{i+1}-x_i|\geq \sum_{j=1}^{M-1} |y_{j+1}-y_{j}|$$ for any subsequence $(y_j)_{j=1}^{M}$ of $(x_i)$.

This more general result would be useful if you wanted $$x_1+\cdots+x_5=25\\ x_6+\cdots+x_{10}=41\\x_{11}+\cdots+{x_{15}}=32.$$
Then you'd know you had a subsequence $y_1,y_2,y_3$ such that $y_1\leq 5, y_2\geq 9,y_3\leq 6,$ so this lemma means that the we have:
$$\sum |x_{i+1}-x_{i}|\geq |5-9|+|9-6|=7$$
and we can get that value with $(5,5,5,5,5,\,8,8,8,8,9,\,7,7,6,6,6)$.

The general rule for generating a solution is, for each block, determine the average. If the average is an integer, we set each of the $x_i$ to that average. If the average in the block is not an integer, we can write the average as $m+\frac{k}{B}$ where $B$ is the size of the block, $m$ is and integer, and $1\leq k <B$. Then we can choose $k$ of the values as $m+1$ and $B-k$ values as $m$.
The only tricky part is when, for two blocks consecutive, if you have non-integers averages and the $m$ values are the same. Then which order you place the $x_i$ is dependent on the blocks around you.
For example, if you want: $$x_1+x_2+x_3=8\\x_{4}+x_{5}+x_{6}=7\\x_{7}+x_{8}+x_{9}=5$$
In this case, which order to put the $x_1,\dots,x_6$ is determined by the value if $5$ of the next block, so you have:
$$(x_i)=(2,3,3,\quad 3,2,2,\quad 2,2,1)$$
But if you wanted $x_{7}+x_{8}+x_{9}=10$ the you'd have:
$$(x_i)=(3,3,2,\quad 2,2,3,\quad 3,3,4)$$
