China Southeastern Mathematical Olympiad

We prove for $n\ge 4$. If the permutations $X_n=(x_1,x_2,\dots ,x_n)$ of $1,2,\dots ,n$ consist of a set $A$, and $f(X_n)=x_1+2x_2+3x_3+\cdots +n{x}_n$, $M_n=\{f(X)\mid X\in A\}$, then $|M_n|=\frac{n^3-n+6}{6}$.

Using mathematical induction on $n$, we see that $$M_n=\left\{\frac{n(n+1)(n+2)}{6},\frac{n(n+1)(n+2)}{6}+1,\dots ,\frac{n(n+1)(2n+1)}{6}\right\}$$ For $n=4$, by arranging inequality, one can see the smallest number of $M$ is $f(\{4,3,2,1\})=20$, and the biggest number is $f(\{1,2,3,4\})=30$. Because $$\begin{array}{rl}f(\{3,4,2,1\})& =21,f(\{3,4,1,2\})=22,\\ f(\{4,2,1,3\})& =23,f(\{3,2,4,1\})=24,\\ f(\{2,4,1,3\})& =25,f(\{1,4,3,2\})=26,\\ f(\{1,4,2,3\})& =27,f(\{2,1,4,3\})=28,\\ f(\{1,2,4,3\})& =29,\end{array}$$ we have, $|M_4|=|\{20,21,\dots ,30\}|=11=\frac{4^3-4+6}{6}$.

Suppose that the statement is true for $n-1$ ($n\ge 5$). In the case of $n$, for a permutation $X_{n-1}=(x_1,x_2,\dots ,x_{n-1})$ of $1,2,\dots ,n-1$, let $x_n=n$; then we get a permutation $(x_1,x_2,\dots ,x_{n-1},n)$ of $1,2,\dots ,n$, and so $$\sum _{k=1}^{n}k{x}_k=n^2+\sum _{k=1}^{n-1}k{x}_k.$$ According to the supposition, the value of ${\sum }_{k=1}^{n}k{x}_k$ can be every integer number in the interval $$\left[n^2+\frac{(n-1)n(n+1)}{6},n^2+\frac{(n-1)n(2n-1)}{6}\right]=\left[\frac{n(n^2+5)}{6},\frac{n(n+1)(2n+1)}{6}\right].$$ Let $x_n=1$. Then $$\begin{array}{rl}\sum _{k=1}^{n}k{x}_k& =n+\sum _{k=1}^{n-1}k{x}_k\\ & =n+\sum _{k=1}^{n-1}k(x_k-1)+\frac{n(n-1)}{2}\\ & =\frac{n(n+1)}{2}+\sum _{k=1}^{n-1}k(x_k-1).\end{array}$$ According to the supposition, the value of ${\sum }_{k=1}^{n}k{x}_k$ can be every integer number in the interval $$\left[\frac{n(n+1)}{2}+\frac{(n-1)n(n+1)}{6},\frac{n(n+1)}{2}+\frac{n(n-1)(2n-1)}{6}\right]=\left[\frac{n(n+1)(n+2)}{6},\frac{2n(n^2+2)}{6}\right].$$ Because $\frac{2n(n^2+2)}{6}\ge \frac{n(n^2+5)}{6}$, according to the supposition the value of ${\sum }_{k=1}^{n}k{x}_k$ can be every integer number in the interval $$\left[\frac{n(n+1)(n+2)}{6},\frac{n(n+1)(2n+1)}{6}\right].$$ The statement is also true for $n$. Since $$\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)(n+2)}{6}=\frac{n^3-n+6}{6},$$ one can see that $|M_n|=\frac{n^3-n+6}{6}+1$.

In particular, $|M_9|=121$.