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 4 of 4: Cross the interval

Previous step Next step

In plain words

Cross the interval

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

Detailed analysis

Reverse an ordering by adjacent swaps. Along this finite path, if no weighted sum lay in the target interval, a jump from below to above would have size strictly greater than $n+1$ , contradicting the previous bound. The ordering at the crossing is the required permutation.