设 $n$ 是正整数，$a_{1}, \ldots, a_{n} \in\{0,1, \cdots, n\}$．对整数 $j(1 \leqslant j \leqslant n)$．定义 $b_j$ 为集合 $\left\{i | i \in\{1, \cdots, n\}, a_{i} \geqslant j\right\}$ 的元素个数．例如：当 $n =3$ 时，若 $a_{1}=1, a_{2}=2, a_{3}=1$，则对应的 $b_{1}=3,b_{2}=1, b_{3}=0$．
（1）证明：$\displaystyle \sum\limits_{i=1}^{n}\left(i+a_{i}\right)^{2} \geqslant \sum_{i=1}^{n}\left(i+b_{i}\right)^{2}$；
（2）证明：若整数 $k \geqslant 3$，则 $\displaystyle \sum\limits_{i=1}^{n}\left(i+a_{i}\right)^{k} \geqslant \sum_{i=1}^{n}\left(i+b_{i}\right)^{k}$．
（1）证明：$\displaystyle \sum\limits_{i=1}^{n}\left(i+a_{i}\right)^{2} \geqslant \sum_{i=1}^{n}\left(i+b_{i}\right)^{2}$；
（2）证明：若整数 $k \geqslant 3$，则 $\displaystyle \sum\limits_{i=1}^{n}\left(i+a_{i}\right)^{k} \geqslant \sum_{i=1}^{n}\left(i+b_{i}\right)^{k}$．
【难度】
【出处】
2016第15届CGMO试题
【标注】
【答案】
略
【解析】
证法一
设 $c_{1} \geqslant \cdots \geqslant c_{n}$ 是 $a_{1}, \ldots, a_{n}$ 按降序的排列．显然 $b_j$ 等于集合 $\left\{i | i \in\{1, \cdots, n\}, c_{i} \geqslant j\right\}$ 的元素个数．下面先证明两个多重集 $\left\{1+c_{1}, \cdots, n+c_{n}\right\}=\left\{1+b_{1}, \cdots, n+b_{n}\right\}$ ①
以平而直角坐标系的 $(0,0), (0, n), (n, n), (n, 0)$ 四个点为顶点构造一个 $n\times n$ 的方格表，由左至右分别记为第 $1,\cdots,n$ 列，由下至上分别记为第 $1, \cdots, n$ 行．
对每个 $i=1, \cdots, n$，将第 $i$ 列由下至上的前 $c_i$ 个格子涂黑，这样由 $b_j$ 的性质知第 $j$ 行由左至右的前 $b_j$ 个方格是黑的，剩余方格未被涂色．
由方格表的左上角 $(0, n)$ 开始，画出黑色方格和未涂色方格的分界线，直 到右下角 $(n, 0)$ 为止．设所画出的折线为 $L$，则 $L$ 由 $n$ 条长度为 $1$ 的水平线段和 $n$ 条长度为 $1$ 的竖直线段构成，且从左到右每条水平线段中点的横纵坐标之和依次为 $1+c_{1}-\frac{1}{2}, \cdots, n+c_{n}-\frac{1}{2}$，从下到上每条竖直线段上端点的横纵坐标之和依次为 $1+b_{1}-\frac{1}{2}, \cdots, n+b_{n}-\frac{1}{2}$．
对任意正整数 $r$，作直线 $l_{r} : x+y=r-\dfrac{1}{2}$，则由于 $(0, n)$ 和 $(n, 0)$ 必在直线的同一侧，故折线在横向穿过 $l_r$ 的次数等于在纵向穿过 $l_r$ 的次数，结合穿过 $l_r$ 必然是在长度为 $1$ 的线段中点，以及 $r$ 的任意性，得多重集 $\left\{1+c_{1}-\dfrac{1}{2}, \cdots, n+c_{n}-\dfrac{1}{2}\right\}=\left\{1+b_{1}-\dfrac{1}{2}, \cdots, n+b_{n}-\dfrac{1}{2}\right\}$，故 ① 成立．
由于 $c_{1}, \cdots, c_{n}$ 和 $1, \cdots, n$ 为逆序．故对任意整数 $k\geqslant 2$，我们有 $\displaystyle \sum\limits_{i=1}^n(i+a_i)^k=\sum_{i=1}^n\sum_{s=0}^kC_k^si^sa_i^{k-s}=\sum_{s=0}^k\sum_{i=1}^nC_k^si^sa_{i}^{k-s}\geqslant \sum_{s=0}^k\sum_{i=1}^nC_k^si^sc_i^{k-s}$（排序不等式）$\displaystyle =\sum\limits_{i=1}^n\sum_{s=0}^kC_k^si^sc_i^{k-s}=\sum_{i=1}^n(i+c_i)^k=\sum_{i=1}^n(i+b_i)^k$
其中 $k=2$ 即为第一问，$k\geqslant 3$ 即为第二问，证毕．
证法二
（1）注意到 $\displaystyle b_j=\sum\limits_{i, a_i \geqslant j} 1$，直接计算可得
$\displaystyle \sum\limits_{j=1}^{n}\left(j+b_{j}\right)^{2}=\sum_{j=1}^{n} b_{j}^{2}+2 \sum_{j=1}^{n} j b_{j}+\sum_{j=1}^{n} j^{2}=\sum_{j=1}^{n} \sum_{a_{i_1} \geqslant j} \sum_{a_{i_2} \geqslant j} 1+2 \sum_{j=1}^{n} j \sum_{a_i \geqslant j} 1+\sum_{j=1}^{n} j^{2}$
$\displaystyle =\sum\limits_{i_1, i_{2}} \sum_{j \leqslant \min \left(a_{i_1}, a_{i_2}\right)} 1+2 \sum_{i=1}^{n} \sum_{j \leqslant a_{i}} j+\sum_{j=1}^{n} j^{2}=\sum_{i_1, i_{2}} \min \left(a_{i_1}, a_{i_2}\right)+2 \sum_{i=1}^{n}\left(1+\cdots+a_{i}\right)+\sum_{j=1}^{n} j^{2}$
$\displaystyle =\sum\limits_{i=1}^{n} a_{i}+2 \sum_{i_{i}<i_{2}} \min \left(a_{i_{1}}, a_{i_{2}}\right)+\sum_{i=1}^{n} a_{i}\left(a_{i}+1\right)+\sum_{j=1}^{n} j^{2}\leqslant \sum_{i=1}^{n} a_{i}+2 \sum_{i_{i}<i_{2}} a_{i_{2}}+\sum_{i=1}^{n} a_{i}\left(a_{i}+1\right)+\sum_{j=1}^{n} j^{2}$
$\displaystyle =\sum\limits_{i=1}^{n} a_{i}+2 \sum_{i_{2}=1}^{n} \sum_{i_{1}<i_{2}} a_{i_{2}}+\sum_{i=1}^{n} a_{i}\left(a_{i}+1\right)+\sum_{j=1}^{n} j^{2}=\sum_{i=1}^{n} a_{i}+2 \sum_{i_{i}=1}^{n}\left(i_{2}-1\right) a_{i_{2}}+\sum_{i=1}^{n} a_{i}\left(a_{i}+1\right)+\sum_{j=1}^{n} j^{2}$
$\displaystyle =\sum\limits_{i=1}^{n}\left(i+a_{i}\right)^{2}$．
（2）将 $a_{1}, \cdots, a_{n}$ 从大到小排列为 $\overline{a}_{1} \geqslant \cdots \geqslant \overline{a}_{n}$．由 $b_j$ 的定义可知，$\overline{a}_{i} \geqslant j$ 当且仅当 $i \leqslant b_{j}$．考虑集合 $S=\left\{(i, j) | 1 \leqslant i \leqslant n, 1 \leqslant j \leqslant \overline{a}_{i}\right\}$，则 $S=\left\{(i, j) | 1 \leqslant j \leqslant n, 1 \leqslant i \leqslant b_{j}\right\}$．
对任何一元函数 $f(x)$，令 $\displaystyle F=\sum\limits_{(i, j) \in s}(f(i+j)-f(i+j-1))$，我们用两种方法来计算 $F$．
一方面，注意到 $S=\bigcup_{i=1}^{n}\left\{(i, j) | 1 \leqslant j \leqslant \overline{a}_{i}\right\}$，则有 $\displaystyle F=\sum\limits_{i=1}^{n} \sum_{j=1}^{\overline{a}_{i}}(f(i+j)-f(i+j-1))=\sum_{i=1}^{n}\left(f\left(i+\overline{a}_{i}\right)-f(i)\right)$
另一方面，注意到 $S=\bigcup_{j=1}^{n}\left\{(i, j) | 1 \leqslant i \leqslant b_{j}\right\}$，则有 $\displaystyle F=\sum\limits_{j=1}^{n} \sum_{i=1}^{b_j}(f(i+j)-f(i+j-1))=\sum_{j=1}^{n}\left(f\left(j+b_{j}\right)-f(j)\right)$
结合这两方面的计算结果，可得 $\displaystyle \sum\limits_{i=1}^{n} f\left(i+\overline{a}_{i}\right)=\sum_{i=1}^{n} f\left(i+b_{i}\right)$
特别地，取 $f(x)=x^{k}$，则有 $\displaystyle \sum\limits_{i=1}^{n}\left(i+\overline{a}_{i}\right)^{k}=\sum_{i=1}^{n}\left(i+b_{i}\right)^{k}$．
最后，对正整数 $k$，利用排序不等式可得
$\displaystyle \sum\limits_{i=1}^{n}\left(i+b_{i}\right)^{k}=\sum_{i=1}^{n}\left(i+\overline{a}_{i}\right)^{k}=\sum_{i=1}^{n} \sum_{t=0}^{k} C_{k}^{t} i^{k-t} a_{i}^{-t}=\sum_{t=0}^{k} \sum_{i=1}^{n} C_{k}^{t} i^{k-t} a_{i}^{-t}\leqslant \sum_{t=0}^{k} \sum_{i=1}^{n} \mathrm{C}_{k}^{t} i^{k-t} a_{i}^{t}=\sum_{i=1}^{n} \sum_{t=0}^{k} C_{k}^{t} i^{k-t} a_{i}^{t}=\sum_{i=1}^{n}\left(i+a_{i}\right)^{k}$
这就完成了整个证明
设 $c_{1} \geqslant \cdots \geqslant c_{n}$ 是 $a_{1}, \ldots, a_{n}$ 按降序的排列．显然 $b_j$ 等于集合 $\left\{i | i \in\{1, \cdots, n\}, c_{i} \geqslant j\right\}$ 的元素个数．下面先证明两个多重集 $\left\{1+c_{1}, \cdots, n+c_{n}\right\}=\left\{1+b_{1}, \cdots, n+b_{n}\right\}$ ①
以平而直角坐标系的 $(0,0), (0, n), (n, n), (n, 0)$ 四个点为顶点构造一个 $n\times n$ 的方格表，由左至右分别记为第 $1,\cdots,n$ 列，由下至上分别记为第 $1, \cdots, n$ 行．
对每个 $i=1, \cdots, n$，将第 $i$ 列由下至上的前 $c_i$ 个格子涂黑，这样由 $b_j$ 的性质知第 $j$ 行由左至右的前 $b_j$ 个方格是黑的，剩余方格未被涂色．
由方格表的左上角 $(0, n)$ 开始，画出黑色方格和未涂色方格的分界线，直 到右下角 $(n, 0)$ 为止．设所画出的折线为 $L$，则 $L$ 由 $n$ 条长度为 $1$ 的水平线段和 $n$ 条长度为 $1$ 的竖直线段构成，且从左到右每条水平线段中点的横纵坐标之和依次为 $1+c_{1}-\frac{1}{2}, \cdots, n+c_{n}-\frac{1}{2}$，从下到上每条竖直线段上端点的横纵坐标之和依次为 $1+b_{1}-\frac{1}{2}, \cdots, n+b_{n}-\frac{1}{2}$．
对任意正整数 $r$，作直线 $l_{r} : x+y=r-\dfrac{1}{2}$，则由于 $(0, n)$ 和 $(n, 0)$ 必在直线的同一侧，故折线在横向穿过 $l_r$ 的次数等于在纵向穿过 $l_r$ 的次数，结合穿过 $l_r$ 必然是在长度为 $1$ 的线段中点，以及 $r$ 的任意性，得多重集 $\left\{1+c_{1}-\dfrac{1}{2}, \cdots, n+c_{n}-\dfrac{1}{2}\right\}=\left\{1+b_{1}-\dfrac{1}{2}, \cdots, n+b_{n}-\dfrac{1}{2}\right\}$，故 ① 成立．
由于 $c_{1}, \cdots, c_{n}$ 和 $1, \cdots, n$ 为逆序．故对任意整数 $k\geqslant 2$，我们有 $\displaystyle \sum\limits_{i=1}^n(i+a_i)^k=\sum_{i=1}^n\sum_{s=0}^kC_k^si^sa_i^{k-s}=\sum_{s=0}^k\sum_{i=1}^nC_k^si^sa_{i}^{k-s}\geqslant \sum_{s=0}^k\sum_{i=1}^nC_k^si^sc_i^{k-s}$（排序不等式）$\displaystyle =\sum\limits_{i=1}^n\sum_{s=0}^kC_k^si^sc_i^{k-s}=\sum_{i=1}^n(i+c_i)^k=\sum_{i=1}^n(i+b_i)^k$
其中 $k=2$ 即为第一问，$k\geqslant 3$ 即为第二问，证毕．
证法二
（1）注意到 $\displaystyle b_j=\sum\limits_{i, a_i \geqslant j} 1$，直接计算可得
$\displaystyle \sum\limits_{j=1}^{n}\left(j+b_{j}\right)^{2}=\sum_{j=1}^{n} b_{j}^{2}+2 \sum_{j=1}^{n} j b_{j}+\sum_{j=1}^{n} j^{2}=\sum_{j=1}^{n} \sum_{a_{i_1} \geqslant j} \sum_{a_{i_2} \geqslant j} 1+2 \sum_{j=1}^{n} j \sum_{a_i \geqslant j} 1+\sum_{j=1}^{n} j^{2}$
$\displaystyle =\sum\limits_{i_1, i_{2}} \sum_{j \leqslant \min \left(a_{i_1}, a_{i_2}\right)} 1+2 \sum_{i=1}^{n} \sum_{j \leqslant a_{i}} j+\sum_{j=1}^{n} j^{2}=\sum_{i_1, i_{2}} \min \left(a_{i_1}, a_{i_2}\right)+2 \sum_{i=1}^{n}\left(1+\cdots+a_{i}\right)+\sum_{j=1}^{n} j^{2}$
$\displaystyle =\sum\limits_{i=1}^{n} a_{i}+2 \sum_{i_{i}<i_{2}} \min \left(a_{i_{1}}, a_{i_{2}}\right)+\sum_{i=1}^{n} a_{i}\left(a_{i}+1\right)+\sum_{j=1}^{n} j^{2}\leqslant \sum_{i=1}^{n} a_{i}+2 \sum_{i_{i}<i_{2}} a_{i_{2}}+\sum_{i=1}^{n} a_{i}\left(a_{i}+1\right)+\sum_{j=1}^{n} j^{2}$
$\displaystyle =\sum\limits_{i=1}^{n} a_{i}+2 \sum_{i_{2}=1}^{n} \sum_{i_{1}<i_{2}} a_{i_{2}}+\sum_{i=1}^{n} a_{i}\left(a_{i}+1\right)+\sum_{j=1}^{n} j^{2}=\sum_{i=1}^{n} a_{i}+2 \sum_{i_{i}=1}^{n}\left(i_{2}-1\right) a_{i_{2}}+\sum_{i=1}^{n} a_{i}\left(a_{i}+1\right)+\sum_{j=1}^{n} j^{2}$
$\displaystyle =\sum\limits_{i=1}^{n}\left(i+a_{i}\right)^{2}$．
（2）将 $a_{1}, \cdots, a_{n}$ 从大到小排列为 $\overline{a}_{1} \geqslant \cdots \geqslant \overline{a}_{n}$．由 $b_j$ 的定义可知，$\overline{a}_{i} \geqslant j$ 当且仅当 $i \leqslant b_{j}$．考虑集合 $S=\left\{(i, j) | 1 \leqslant i \leqslant n, 1 \leqslant j \leqslant \overline{a}_{i}\right\}$，则 $S=\left\{(i, j) | 1 \leqslant j \leqslant n, 1 \leqslant i \leqslant b_{j}\right\}$．
对任何一元函数 $f(x)$，令 $\displaystyle F=\sum\limits_{(i, j) \in s}(f(i+j)-f(i+j-1))$，我们用两种方法来计算 $F$．
一方面，注意到 $S=\bigcup_{i=1}^{n}\left\{(i, j) | 1 \leqslant j \leqslant \overline{a}_{i}\right\}$，则有 $\displaystyle F=\sum\limits_{i=1}^{n} \sum_{j=1}^{\overline{a}_{i}}(f(i+j)-f(i+j-1))=\sum_{i=1}^{n}\left(f\left(i+\overline{a}_{i}\right)-f(i)\right)$
另一方面，注意到 $S=\bigcup_{j=1}^{n}\left\{(i, j) | 1 \leqslant i \leqslant b_{j}\right\}$，则有 $\displaystyle F=\sum\limits_{j=1}^{n} \sum_{i=1}^{b_j}(f(i+j)-f(i+j-1))=\sum_{j=1}^{n}\left(f\left(j+b_{j}\right)-f(j)\right)$
结合这两方面的计算结果，可得 $\displaystyle \sum\limits_{i=1}^{n} f\left(i+\overline{a}_{i}\right)=\sum_{i=1}^{n} f\left(i+b_{i}\right)$
特别地，取 $f(x)=x^{k}$，则有 $\displaystyle \sum\limits_{i=1}^{n}\left(i+\overline{a}_{i}\right)^{k}=\sum_{i=1}^{n}\left(i+b_{i}\right)^{k}$．
最后，对正整数 $k$，利用排序不等式可得
$\displaystyle \sum\limits_{i=1}^{n}\left(i+b_{i}\right)^{k}=\sum_{i=1}^{n}\left(i+\overline{a}_{i}\right)^{k}=\sum_{i=1}^{n} \sum_{t=0}^{k} C_{k}^{t} i^{k-t} a_{i}^{-t}=\sum_{t=0}^{k} \sum_{i=1}^{n} C_{k}^{t} i^{k-t} a_{i}^{-t}\leqslant \sum_{t=0}^{k} \sum_{i=1}^{n} \mathrm{C}_{k}^{t} i^{k-t} a_{i}^{t}=\sum_{i=1}^{n} \sum_{t=0}^{k} C_{k}^{t} i^{k-t} a_{i}^{t}=\sum_{i=1}^{n}\left(i+a_{i}\right)^{k}$
这就完成了整个证明
答案
解析
备注
