设 $1,2,\cdots,9$ 的所有排列 $X=(x_1,x_2,\cdots,x_9)$ 的集合为 $A$；$\forall X\in A$，记 $f(X)=x_1+2x_2+3x_3+\cdots+9x_9$，$M=\{f(X)|X\in A\}$；求 $|M|$．（其中 $|M|$ 表示集合 $M$ 的元素个数）
【难度】
【出处】
2009中国东南数学奥林匹克试题
【标注】
【答案】
略
【解析】
我们一般地证明，若 $n\geqslant 4$，对于前 $n$ 个正整数 $1,2,\cdots,n$ 的所有排列 $X_n=(x_1,x_2,\cdots,x_n)$ 构成的集合 $A$，记 $f(X_n)=x_1+2x_2+3x_3+\cdots+nx_n,M_n=\{f(X)|X\in A\}$，则 $|M_n|=\dfrac{n^3-n+6}{6}$．
下面用数学归纳法证明：
$M_n=\left\{\dfrac{n(n+1)(n+2)}{6},\dfrac{n(n+1)(n+2)}{6}+1,\cdots,\dfrac{n(n+1)(2n+1)}{6}\right\}$．
当 $n=4$ 时，由排序不等式知，集合 $M$ 中的最小元素是 $f(\{4,3,2,1\})=20$，最大元素是 $f(\{1,2,3,4\})=30$．又可知
$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$
所以，$M_4=\{20,21,\cdots,30\}$ 共有 $\dfrac{4^3-4+6}{6}=11$（个）元素．因此，$n=4$ 时命题成立．
假设命题在 $n-1(n\geqslant 5)$ 时成立；考虑命题在 $n$ 时的情况．对于 $1,2,\cdots,n-1$ 的任一排列 $X_{n-1}=(x_1,x_2,\cdots,x_{n-1})$，恒取 $x_n=n$，得到 $1,2,\cdots,n$ 一个排列 $x_1,x_2,\cdots,x_{n-1},n
$，则 $\displaystyle \sum\limits_{k=1}^nkx_k=n^2+\sum_{k=1}^{n-1}kx_k$．由归纳假设知，此时 $\displaystyle \sum\limits_{k=1}^nkx_k$ 取遍区间
$\left[n^2+\dfrac{(n-1)n(n+1)}{6},n^2+\dfrac{(n-1)n(2n-1)}{6}\right]=\left[\dfrac{n(n^2+5)}{6},\dfrac{n(n+1)(2n+1)}{6}\right]$ 上所有整数．
再令 $x_n=1$，则
$\displaystyle \sum\limits_{k=1}^nkx_k=n+\sum_{k=1}^{n-1}kx_k=n+\sum_{k=1}^{n-1}k(x_k-1)+\dfrac{n(n-1)}{2}=\dfrac{n(n+1)}{2}+\sum_{k=1}^{n-1}k(x_k-1)$．
再由归纳假设知，$\displaystyle \sum\limits_{k=1}^nkx_k$ 取遍区间
$\left[\dfrac{n(n+1)}{2}+\dfrac{(n-1)n(n+1)}{6},\dfrac{n(n+1)}{2}+\dfrac{n(n-1)(2n-1)}{6}\right]=\left[\dfrac{n(n+1)(n+2)}{6},\dfrac{2n(n^2+2)}{6}\right]$
上的所有整数．
因为 $\dfrac{2n(n^2+2)}{6}\geqslant\dfrac{n(n^2+5)}{6}$，所以 $\displaystyle \sum\limits_{k=1}^nkx_k$ 取遍区间 $\left[\dfrac{n(n+1)(n+2)}{6},\dfrac{2n(n^2+2)}{6}\right]$ 上的所有整数，即命题对 $n$ 也成立．由数学归纳法知，命题成立．
由于 $\dfrac{n(n+1)(2n+1)}{6}-\dfrac{n(n+1)(n+2)}{6}=\dfrac{(n^3-n+6)}{6}$
从而，集合 $M_n$ 的元素个数为 $\dfrac{n^3-n+6}{6}$．特别是，当 $n=9$ 时，$|M|=|M_9|=121$．
下面用数学归纳法证明：
$M_n=\left\{\dfrac{n(n+1)(n+2)}{6},\dfrac{n(n+1)(n+2)}{6}+1,\cdots,\dfrac{n(n+1)(2n+1)}{6}\right\}$．
当 $n=4$ 时，由排序不等式知，集合 $M$ 中的最小元素是 $f(\{4,3,2,1\})=20$，最大元素是 $f(\{1,2,3,4\})=30$．又可知
$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$
所以，$M_4=\{20,21,\cdots,30\}$ 共有 $\dfrac{4^3-4+6}{6}=11$（个）元素．因此，$n=4$ 时命题成立．
假设命题在 $n-1(n\geqslant 5)$ 时成立；考虑命题在 $n$ 时的情况．对于 $1,2,\cdots,n-1$ 的任一排列 $X_{n-1}=(x_1,x_2,\cdots,x_{n-1})$，恒取 $x_n=n$，得到 $1,2,\cdots,n$ 一个排列 $x_1,x_2,\cdots,x_{n-1},n
$，则 $\displaystyle \sum\limits_{k=1}^nkx_k=n^2+\sum_{k=1}^{n-1}kx_k$．由归纳假设知，此时 $\displaystyle \sum\limits_{k=1}^nkx_k$ 取遍区间
$\left[n^2+\dfrac{(n-1)n(n+1)}{6},n^2+\dfrac{(n-1)n(2n-1)}{6}\right]=\left[\dfrac{n(n^2+5)}{6},\dfrac{n(n+1)(2n+1)}{6}\right]$ 上所有整数．
再令 $x_n=1$，则
$\displaystyle \sum\limits_{k=1}^nkx_k=n+\sum_{k=1}^{n-1}kx_k=n+\sum_{k=1}^{n-1}k(x_k-1)+\dfrac{n(n-1)}{2}=\dfrac{n(n+1)}{2}+\sum_{k=1}^{n-1}k(x_k-1)$．
再由归纳假设知，$\displaystyle \sum\limits_{k=1}^nkx_k$ 取遍区间
$\left[\dfrac{n(n+1)}{2}+\dfrac{(n-1)n(n+1)}{6},\dfrac{n(n+1)}{2}+\dfrac{n(n-1)(2n-1)}{6}\right]=\left[\dfrac{n(n+1)(n+2)}{6},\dfrac{2n(n^2+2)}{6}\right]$
上的所有整数．
因为 $\dfrac{2n(n^2+2)}{6}\geqslant\dfrac{n(n^2+5)}{6}$，所以 $\displaystyle \sum\limits_{k=1}^nkx_k$ 取遍区间 $\left[\dfrac{n(n+1)(n+2)}{6},\dfrac{2n(n^2+2)}{6}\right]$ 上的所有整数，即命题对 $n$ 也成立．由数学归纳法知，命题成立．
由于 $\dfrac{n(n+1)(2n+1)}{6}-\dfrac{n(n+1)(n+2)}{6}=\dfrac{(n^3-n+6)}{6}$
从而，集合 $M_n$ 的元素个数为 $\dfrac{n^3-n+6}{6}$．特别是，当 $n=9$ 时，$|M|=|M_9|=121$．
答案
解析
备注
