设正整数 $m,n\geqslant 2$，对于任一个 $n$ 元整数集 $A=\{a_1,a_2,\cdots,a_n\}$，取每一对不同的数 $a_i,a_j(j>i)$，作差 $a_j-a_i$，由这 $C_n^2$ 个差按从小到大顺序排成的一个数列，称为集合 $A$ 的"衍生数列"，记为 $\overline{A}$．衍生数列 $\overline{A}$ 中能被 $m$ 整除的数的个数记为 $\overline{A}(m)$．
证明：对于任一正整数 $m\geqslant 2$，$n$ 元整数集 $A=\{a_1,a_2,\cdots,a_n\}$ 及集合 $B=\{1,2,\cdots,n\}$ 所对应的"衍生数列" $\overline{A}$ 及 $\overline{B}$，满足不等式 $\overline{A}(m)\geqslant\overline{B}(m)$．
证明：对于任一正整数 $m\geqslant 2$，$n$ 元整数集 $A=\{a_1,a_2,\cdots,a_n\}$ 及集合 $B=\{1,2,\cdots,n\}$ 所对应的"衍生数列" $\overline{A}$ 及 $\overline{B}$，满足不等式 $\overline{A}(m)\geqslant\overline{B}(m)$．
【难度】
【出处】
2008中国东南数学奥林匹克试题
【标注】
【答案】
略
【解析】
对于给定的正整数 $m\geqslant 2$，若整数 $x$ 被 $m$ 除得的余数为 $i$，$i\in\{0,1,\cdots,m-1\}$，则称 $x$ 属于模 $m$ 的剩余类 $K_i$．
设 $A$ 的元素中属于 $K_i$ 的数有 $n_i(i=0,1,2,\cdots,m-1)$ 个，而集合 $B=\{1,2,\cdots,n\}$ 的元素属于 $K_i$ 的数有 $n_i^\prime(i=0,1,2,\cdots,m-1)$ 个，则 $\displaystyle \sum\limits_{i=0}^{m-1}n_i=\sum_{i=0}^{m-1} n^{\prime}_i=n$ ①
易知，对任意 $i,j$，$n_i^\prime$ 与 $n_j^\prime$ 至多相差 $1$，且 $x-y$ 是 $m$ 的倍数当且仅当两数 $x,y$ 属于模 $m$ 的同一个剩余类．对于剩余类 $K_i$ 中的任一对数 $a_i,a_j$，有 $m|a_j-a_i$，故属于 $K_i$ 中 $n_i$ 个数，共作成 $C_{n_i}^2$ 个 $m$ 的倍数，考虑所有的 $i$，则 $\displaystyle \overline{A}(m)=\sum\limits_{i=0}^{m-1}C_{n_i}^2$，类似得 $\displaystyle \overline{B}(m)=\sum\limits_{i=0}^{m-1}C_{n_i^\prime}^2$．
为证本题，只要证 $\displaystyle \sum\limits_{i=0}^{m-1}C_{n_i}^2\geqslant\sum_{i=0}^{m-1}C_{n_i^{\prime}}^2$，化简后，即要证 $\displaystyle \sum\limits_{i=0}^{m-1}{n_i}^2\geqslant\sum_{i=0}^{m-1}{n_i^{\prime}}^2$ ②
据 ① 易知，若对任意 $i,j,|n_i-n_j|\leqslant 1$，则 $n_0,n_1,\cdots,n_{m-1}$ 与 $n^\prime_0,n^\prime_1,\cdots,n^\prime_{m-1}$ 就是同一组数（至多只有顺序不同），这时 ② 式将取得等号．
若存在 $i,j$，使 $n_i-n_j\geqslant 2$，这时将 $n_i,n_j$ 两数调整为 $\overline{n}_i,\overline{n}_j$，其中 $\overline{n}_i=n_i-1,\overline{n}_j=n_j+1$，其中元素不变，则 $n_i+n_j=\overline{n}_i+\overline{n}_j$，由于 $(n_i^2+n_j^2)-(\overline{n}_i^2+\overline{n}_j^2)=2(n_i-n_j-1)>0$
故调整后 ② 式左边的和值将减少，因此 ② 式取得最小值当且仅当 $n_0,n_1,\cdots,n_{m-1}$ 与 $n^\prime_0,n^\prime_1,\cdots,n^\prime_{m-1}$ 为同一组数（至少只有顺序不同），即 ② 成立，因此结论得证．
设 $A$ 的元素中属于 $K_i$ 的数有 $n_i(i=0,1,2,\cdots,m-1)$ 个，而集合 $B=\{1,2,\cdots,n\}$ 的元素属于 $K_i$ 的数有 $n_i^\prime(i=0,1,2,\cdots,m-1)$ 个，则 $\displaystyle \sum\limits_{i=0}^{m-1}n_i=\sum_{i=0}^{m-1} n^{\prime}_i=n$ ①
易知，对任意 $i,j$，$n_i^\prime$ 与 $n_j^\prime$ 至多相差 $1$，且 $x-y$ 是 $m$ 的倍数当且仅当两数 $x,y$ 属于模 $m$ 的同一个剩余类．对于剩余类 $K_i$ 中的任一对数 $a_i,a_j$，有 $m|a_j-a_i$，故属于 $K_i$ 中 $n_i$ 个数，共作成 $C_{n_i}^2$ 个 $m$ 的倍数，考虑所有的 $i$，则 $\displaystyle \overline{A}(m)=\sum\limits_{i=0}^{m-1}C_{n_i}^2$，类似得 $\displaystyle \overline{B}(m)=\sum\limits_{i=0}^{m-1}C_{n_i^\prime}^2$．
为证本题，只要证 $\displaystyle \sum\limits_{i=0}^{m-1}C_{n_i}^2\geqslant\sum_{i=0}^{m-1}C_{n_i^{\prime}}^2$，化简后，即要证 $\displaystyle \sum\limits_{i=0}^{m-1}{n_i}^2\geqslant\sum_{i=0}^{m-1}{n_i^{\prime}}^2$ ②
据 ① 易知，若对任意 $i,j,|n_i-n_j|\leqslant 1$，则 $n_0,n_1,\cdots,n_{m-1}$ 与 $n^\prime_0,n^\prime_1,\cdots,n^\prime_{m-1}$ 就是同一组数（至多只有顺序不同），这时 ② 式将取得等号．
若存在 $i,j$，使 $n_i-n_j\geqslant 2$，这时将 $n_i,n_j$ 两数调整为 $\overline{n}_i,\overline{n}_j$，其中 $\overline{n}_i=n_i-1,\overline{n}_j=n_j+1$，其中元素不变，则 $n_i+n_j=\overline{n}_i+\overline{n}_j$，由于 $(n_i^2+n_j^2)-(\overline{n}_i^2+\overline{n}_j^2)=2(n_i-n_j-1)>0$
故调整后 ② 式左边的和值将减少，因此 ② 式取得最小值当且仅当 $n_0,n_1,\cdots,n_{m-1}$ 与 $n^\prime_0,n^\prime_1,\cdots,n^\prime_{m-1}$ 为同一组数（至少只有顺序不同），即 ② 成立，因此结论得证．
答案
解析
备注
