Problem 3

Let

x_1,x_2,\ldots,x_n

be real numbers satisfying

|x_1+x_2+\cdots+x_n|=1

and

|x_i|\le(n+1)/2

for every

i

. Show that there is a permutation

y_1,\ldots,y_n

of the

x_i

such that

|y_1+2y_2+\cdots+ny_n|\le(n+1)/2

Step 3 of 4: Connect by adjacent transpositions

In plain words

Connect by adjacent transpositions

|\Delta W|=|a-b|\le n+1

Detailed analysis

An adjacent swap at positions $k,k+1$ changes the weighted sum by $a-b$ in absolute value. Since $|a|,|b|\le(n+1)/2$ , this change is at most $n+1$ .