$|(y_1+...+ny_n)+(ny_1+...+y_n)|=(n+1)(1)=n+1$ --> not to fulfil our conditon, $|y_1+...+ny_n|$ and $|ny_1+...+y_n|$ must differ by more $n+1$. Now if we switch 2 neighbouring elements, then $|y_1+...+ny_n|$ changes by $k.(y_k-y_{k-1})+(k-1)(y_{k-1}-y_k) = 1(y_{k}-y_{k-1})$, which is at most $n+1$. And this is a contradiction, since there would be no way to cross the gap, but both ends can be attained by switching. The idea in this problem helps a lot in finding the solution.

I did the hard way by adding all possible permutations together to get their average, which is $ (n+1)/2$. And since they are all equal, or at least one of the permutations is greater than average, which means there exist a permutation less than average. Am I right?

who has another solution?

I thought this problem is pretty trivial, maybe I missed something So obviously if $x_1=x_2=...=x_n$, then the statement is true, and we actually have a equality. The obvious answer to the general solution of course is to arrange the $n$ elements in increasing order, let $y_1$ be the largest of the elements, and $y_n$ be the smallest, i.e. $y_n\le y_{n-1}\le ... \le y_1$ WLOG assume $x_1+x_2+...+x_n=1$ observe now that the average of the elements is $x_1+x_2+...+x_n=\frac{1}{n}$, so let $y_1=\frac{1}{n}+q$ for some some value $q$. This $y_1$ must exist since all $n$ elements cannot be all less than $1/n$ which is the average. And let us for the sake of argument put the extra $q$ at any place other than the first position, say , let $y_n=(1/n)-q$ So the equation now becomes $(q+\frac{1}{n})+2(\frac{1}{n})+3(\frac{1}{n})+...+n(\frac{1}{n}-q)$ $=\frac{n+1}{2}+(1-n)q \le \frac{n+1}{2}$ So apply similar arguments to a more general case, so i will stretch out my arms before I attempt it..., Ok here it is: let $y_1=\frac{1}{n}+q_1$ $y_2=\frac{1}{n}+q_2$ ... $y_k=\frac{1}{n}+q_k$ $y_{k+1}=\frac{1}{n}-q_{k+1}$ .... $y_n=\frac{1}{n}-q_n$ where $q_1 \ge q_2 \ge q_3 \ge ... \ge q_k \ge 0 \ge -q_{k+1}\ge....\ge-q_n$ $q_i \le \frac{n+1}{2}-\frac{1}{n}$ for $i=1,2...,k$, and $-q_i\ge -(\frac{n+1}{2}-\frac{1}{n})$ for $i=k+1,...,n$ Observe $q_1+q_2+q_3+...+q_k-q_{k+1}-....-q_n=0$ Now, $y_1+2y_2+...+ny_n=$ $=\frac{n(n+1)}{2}n+q_1+2q_2+3q_3+...+kq_k-(k+1)q_{k+1}-....-nq_n$ Now, observe $\frac{n+1}{2}-\frac{1}{n}\ge q_1\ge q_2 \ge...\ge q_k\ge0$ And, $\frac{n+1}{2}-\frac{1}{n}\ge q_n\ge q_{n-1}\ge...\ge q_{k+1}\ge0$ But what is $q_1+2q_2+3q_3+...+kq_k-(k+1)q_{k+1}-....-nq_n$? Well it is the following equations added together: $q_1+q_2+q_3+...+q_k-q_{k+1}-....-q_n=0$ +____$q_2+q_3+...+q_k-q_{k+1}-....-q_n=-q_1$ +________$q_3+...+q_k-q_{k+1}-....-q_n=-q_1-q_2$ ..... +_______________$q_k-q_{k+1}-...-q_n=-q_1-q_2-.....-q_{k-1}$ +__________________$-q_{k+1}-...-q_n=-q_{k+1}-...-q_n$ ..... +____________________________$-q_n=-q_n$ So, $q_1+2q_2+3q_3+...+kq_k-(k+1)q_{k+1}-....-nq_n=-(k-1)q_1-(k-2)q_2-....-q_{k_1}-(k+1)q_{k+1}-...-nq_n \le 0$ Therefore, $q_1+2q_2+3q_3+...+kq_k-(k+1)q_{k+1}-....-nq_n\le 0$ So I have proved--or, at least I think I "proved"--that given $x_1+x_2+...+x_n=1$ and, $|x_i| \le (n+1)/2$ then the permutation of {$x_1,...,x_n$}, i.e., $y_n\le y_{n-1}\le ... \le y_1$ satisfies $y_1+2y_2+....+ny_n \le (n+1)/2$ Now I want to show this permutation is $\ge -(n+1)/2$

Solution : First case : There exists two permutations $y_1, y_2, \ldots, y_n$, $z_1, z_2, \ldots, z_n$ of set $x_1, x_2, \ldots, x_n$, such that $a:=y_1 + 2y_2 +\ldots + ny_n\geq 0$, $b:=z_1 + 2z_2 +\ldots + nz_n\leq 0$. In this case we can use some elementary transpositions $\sigma_i$ which switches 2 neighbouring elements and sends set $y_1, \ldots, y_n$ to set $z_1, \ldots, z_n$. Note that for every transposition $\tau : (y_i, y_{i+1})\to (y_{i+1}, y_i)$, $|(y_1 + 2y_2 +\ldots + ny_n) - (y_{\sigma(1)} + 2y_{\sigma(2)} +\ldots + ny_{\sigma(n)})|\leq |y_i - y_{i+1}|\leq n+1$. So from continuous principle we know that $a\geq 0$, $b\leq 0$ and so by some permutations we can get to sequence $|t_1 + 2t_2 +\ldots + nt_n|\leq (n+1)/2$. Second case : For every permutation $y_1, y_2, \ldots, y_n$, number $y_1 + 2y_2 +\ldots + ny_n$ is positive. In this case consider cyclic permutation $\sigma : (1, 2, \ldots, n)\to (2, 3, \ldots, 1)$ and if $y_{\sigma^i(1)} + 2y_{\sigma^i(2)} +\ldots + ny_{\sigma^i(n)}> (n+1)/2$ for all $i$, then we can get $\sum_{i=1}^n i = \sum_{i=1}^n(y_{\sigma^i(1)} + 2y_{\sigma^i(2)} +\ldots + ny_{\sigma^i(n)})> n(n+1)/2$. Contadiction. $\Box$

solver6 wrote: Solution : First case : There exists two permutations $y_1, y_2, \ldots, y_n$, $z_1, z_2, \ldots, z_n$ of set $x_1, x_2, \ldots, x_n$, such that $a:=y_1 + 2y_2 +\ldots + ny_n\geq 0$, $b:=z_1 + 2z_2 +\ldots + nz_n\leq 0$. In this case we can use some elementary transpositions $\sigma_i$ which switches 2 neighbouring elements and sends set $y_1, \ldots, y_n$ to set $z_1, \ldots, z_n$. Note that for every transposition $\tau : (y_i, y_{i+1})\to (y_{i+1}, y_i)$, $|(y_1 + 2y_2 +\ldots + ny_n) - (y_{\sigma(1)} + 2y_{\sigma(2)} +\ldots + ny_{\sigma(n)})|\leq |y_i - y_{i+1}|\leq n+1$. So from continuous principle we know that $a\geq 0$, $b\leq 0$ and so by some permutations we can get to sequence $|t_1 + 2t_2 +\ldots + nt_n|\leq (n+1)/2$. Second case : For every permutation $y_1, y_2, \ldots, y_n$, number $y_1 + 2y_2 +\ldots + ny_n$ is positive. In this case consider cyclic permutation $\sigma : (1, 2, \ldots, n)\to (2, 3, \ldots, 1)$ and if $y_{\sigma^i(1)} + 2y_{\sigma^i(2)} +\ldots + ny_{\sigma^i(n)}> (n+1)/2$ for all $i$, then we can get $\sum_{i=1}^n i = \sum_{i=1}^n(y_{\sigma^i(1)} + 2y_{\sigma^i(2)} +\ldots + ny_{\sigma^i(n)})> n(n+1)/2$. Contadiction. $\Box$ What is continuous principle?

Beautiful problem! Here's my solution: Let $\sigma$ denote some permutation $(y_1,y_2, \dots ,y_n)$ of $(x_1,x_2, \dots ,x_n)$, and let $f(\sigma)$ denote the sum $y_1+2y_2 +\dots +ny_n$. WLOG take $x_1+x_2+ \dots +x_n=1$ (if its $-1$, then replace $x_i$ by $-x_i$). Also, let $x_1 \leq x_2 \leq \dots \leq x_n$. Finally, FTSOC assume that $|f(\sigma)|>\frac{n+1}{2}$ for all possible permutations $\sigma$. Let $\sigma_r$ denote the permutation formed by interchanging $y_r$ and $y_{r+1}$ in $\sigma$, for some $r \in [n-1]$. We call such a move (of interchanging adjacent elements) a Pro move. Note that $f(\sigma_r)-f(\sigma)=y_r-y_{r+1}$. Then, by triangle inequality, we get that $$||f(\sigma_r)|-|f(\sigma)|| \leq |f(\sigma_r)-f(\sigma)|=|y_r-y_{r+1}| \leq |y_r|+|y_{r+1}| \leq n+1$$where the last inequality follows from the condition that $|y_i| \leq \frac{n+1}{2}$ for all $i \in [n]$. Our main claim is that $f(\sigma_r)$ and $f(\sigma)$ must have the same sign. Suppose not, and WLOG take $f(\sigma) \geq 0$ and $f(\sigma_r) \leq 0$. By our original assumption, we get $f(\sigma)>\frac{n+1}{2}$ and $f(\sigma_r)<-\frac{n+1}{2}$. Thus, $f(\sigma)-f(\sigma_r)>n+1$, which contradicts the above inequality. Hence, our assumption was wrong, and so $f(\sigma)$ and $f(\sigma_r)$ must have the same sign. Now, let $\sigma_1=(x_1,x_2, \dots ,x_n)$ and $\sigma_2=(x_n,x_{n-1}, \dots ,x_1)$. It's easy to see that there exists a sequence of Pro moves taking $\sigma_1$ to $\sigma_2$ (First take $x_1$ to the end, then take $x_2$ to the end, and so on). By the above para, this means that $f(\sigma_1)$ and $f(\sigma_2)$ have the same sign. Since $x_1 \leq x_2 \leq \dots \leq x_n$, and $x_1+x_2+ \dots +x_n>0$, so we must have $f(\sigma_1)>0$. This means that $f(\sigma_2)$ must also be positive. Also, note that $$f(\sigma_1)+f(\sigma_2)=(n+1)(x_1+x_2+ \dots +x_n)=n+1$$But, using our assumption, we have $f(\sigma_1),f(\sigma_2)>\frac{n+1}{2}$, and so their sum must be greater than $n+1$, a contradiction. Hence, done. $\blacksquare$ REMARKS: The solution was found in the exact opposite order. First the condition to be proved was shown to be equivalent to proving that $f(\sigma_1)$ and $f(\sigma_2)$ have same sign. Then this was shown by defining the Pro moves, and characterizing what happens to $f(\sigma)$ on undergoing a Pro move.

Solution from Twitch Solves ISL: WLOG $\sum x_i = 1$ (by negating $x_i$) and $x_1 \le x_2 \le \dots \le x_n$. Notice that The largest possible value of the sum in question is \[ A = x_1 + 2x_2 + 3x_3 + \dots + nx_n. \]while the smallest value is \[ B = nx_1 + (n-1)x_2 + \dots + x_n. \] Meanwhile, the average value across all permutations is \[ 1 \cdot \frac{n+1}{2} + 2 \cdot \frac{n+1}{2} + \dots + n \cdot \frac{n+1}{2} = \frac{n+1}{2}. \] Now imagine we transform the sum $A$ to the sum $B$, one step at a time, by swapping adjacent elements. Every time we do a swap of two neighboring $u < v$, the sum decreases by \[ (iu + (i+1)v) - (iv + (i+1)u) = v-u < n+1. \]We want to prove we land in the interval \[ I = \left[ -\frac{n+1}{2}, \frac{n+1}{2} \right] \]at some point during this transformation. But since $B \le \frac{n+1}{2} \le A$ (since $\frac{n+1}{2}$ was the average) and our step sizes were at most the length of the interval $I$, this is clear.

It is equivalent to show there is a permutation such that \[ y_1 + 2y_2 + \cdots + ny_n \in \left[-\frac{n+1}{2}, \frac{n+1}{2}\right] \]WLOG let $x_1 < x_2 < \dots < x_n$. Then \[ x_1 + 2x_2 + 3x_3 + \dots + nx_n \]is maximal and \[ x_n + 2x_{n-1} + 3x_{n-2} + \dots + x_1 \]is minimal. Since they sum to $(n + 1) \cdot (x_1 + x_2 + \dots + x_n) = \pm (n + 1)$, either one of them lies in the interval, or they lie on opposite sides of the interval. Claim: Exchanging adjacent $y_i$ and $y_{i+1}$ changes the sum by at most $n+1$. Proof. $((i+1)y_i + iy_{i+1}) - (iy_i + (i+1)y_{i+1}) = y_i - y_{i+1}$ so this follows by the bound. $\blacksquare$ Thus, taking discrete continuity from the smallest permutation to the largest finishes.

Nice AC hybrid. Let $\sigma = (y_1, y_2, \dots, y_n)$ be such a permutation for which the absolute value is minimized, and assume FTSOC it is greater than $\frac{n+1}2$. We can also assume WLOG that the sum in question is greater than $\frac{n+1}2$ (in the other case, repeat the same argument with orderings and directions flipped.) First, I claim that $\sigma$ is inversely sorted. Otherwise, there exist indices $y_i < y_{i+1}$, and by swapping $y_i$ and $y_{i+1}$, the sum $S$ decreases by $$\Delta S = y_{i+1} - y_i \leq n+1.$$However, this means that the newer permutation $\sigma'$ yields a smaller value of $S$, contradiction. Hence $\sigma$ is inversely sorted. On the other hand, by Chebyshev we have $$y_1+2y_2+\cdots+ny_n \leq \frac{n+1}2 (x_1+x_2+\cdots+x_n).$$Notice that we originally assumed that the sum was greater than $\frac{n+1}2$ and any reduction past that value will be a contradiction. This implies that $x_1+x_2+\cdots+x_n = 1$ precisely, so we have the result.

Suppose $n \ge 2$ as $n=1$ is trivial, and WLOG we have $x_1+\ldots+x_n=1$. Then the expected value of $\sum iy_i$ is \[\frac{1+2+\ldots+n}{n} = \frac{n+1}{2}.\] Consider the permutation $\{y_i\}$ for which $\sum iy_i$ is the least possible greater than $\frac{n+1}{2}$ (if there exists one equal to then we're done). Suppose we were to swap $y_k$ and $y_{k+1}$ to decrease $\sum iy_i$ by $y_{k+1}-y_k$, which must be able to happen as we are currently above our expectation, to a value under $\frac{n+1}{2}$ from our minmality assumption. But this jump is at most \[y_{k+1}-y_k = 2 \cdot \frac{n+1}{2} = n+1,\] so our new expression lands inside $\left[-\frac{n+1}{2}, \frac{n+1}{2}\right]$. $\blacksquare$