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 2 of 4: Compare an ordering with its reverse

Previous step Next step

In plain words

Compare an ordering with its reverse

W+W^{\rm rev}=n+1

Detailed analysis

For any ordering define $W=y_1+2y_2+\cdots+ny_n$ . Its reverse has weighted sum $W^{\rm rev}$ . Pairing positions gives $W+W^{\rm rev}=(n+1)(x_1+\cdots+x_n)=n+1$ . Hence either one is already in $[-(n+1)/2,(n+1)/2]$ , or one is above and the other below this interval.