题目

查看数据源：5caecd69210b280220ed1c17

记 $\left[ x \right]$ 表示不超过实数 $x$ 的最大整数。设 ${{x}_{1}},{{x}_{2}},\cdots ,{{x}_{n}}\in \mathbb{R}$，且 $\left[ {{x}_{1}} \right],\left[ {{x}_{2}} \right],\cdots ,\left[ {{x}_{n}} \right]$ 为 $1,2,\cdots ,n$ 的一个排列，其中 $n\geqslant 2$ 为给定整数。求 $\displaystyle \sum\limits_{i=1}^{n-1}{\left[ {{x}_{i+1}}-{{x}_{i}} \right]}$ 的最大值和最小值。

【难度】

【出处】

2014第13届CGMO试题

【标注】

知识点
>
二试代数部分

【答案】

最大值为 $n-1$，最小值为 $2-2n$

【解析】

由于 $\left[ {{x}_{1}}\right],\left[ {{x}_{2}} \right],\cdots ,\left[ {{x}_{n}} \right]$ 为 $1,2,\cdots ,n$ 的一个排列，因此，对任意 $i=1,2,\cdots ,n$，均有 $1\leqslant {{x}_{i}}<n+1$ $E=\left\{{{u}_{i}}{{u}_{j}},{{v}_{i}}{{v}_{j}},{{u}_{i}}{{v}_{j}}\left| i-j\in \left\{\pm 1,\pm 2,\cdots ,\pm \frac{d-1}{2},\frac{m}{2} \right\}(\bmod m) \right.\right\}$ 。特别地 $1\leqslant {{x}_{1}}<n+1$，$1\leqslant {{x}_{n}}<n+1$，。于是，$-n<{{x}_{n}}-{{x}_{1}}<n$ 。
记 $\displaystyle S=\sum\limits_{i=1}^{n-1}{\left[ {{x}_{i+1}}-{{x}_{i}}\right]}$ 。由于 $\left[ {{x}_{i+1}}-{{x}_{i}} \right]\leqslant{{x}_{i+1}}-{{x}_{i}}$，故 $\displaystyle S\leqslant\sum\limits_{i=1}^{n-1}{({{x}_{i+1}}-{{x}_{i}})={{x}_{n}}-{{x}_{1}}<n}$ 。又 $S$ 为整数，知 $S\leqslant n-1$ 。另一方面，由于 $\left[ {{x}_{i+1}}-{{x}_{i}} \right]>{{x}_{i+1}}-{{x}_{i}}-1$，
故 $\displaystyle S>\sum\limits_{i=1}^{n-1}{({{x}_{i+1}}-{{x}_{i}}-1)}={{x}_{n}}-{{x}_{1}}-(n-1)$ 。又 $S$ 为整数，知 $S\geqslant 2-2n$ 。令 ${{x}_{i}}=i(i=1,2,\cdots ,n)$，得 $\displaystyle \sum\limits_{i=1}^{n-1}{\left[{{x}_{i+1}}-{{x}_{i}} \right]=n-1}$ 。令 ${{x}_{i}}=n+1-i+\frac{1}{1+i}(i=1,2,\cdots,n)$，则对任意的 $i=1,2,\cdots ,n-1$，有
$\begin{align}
& \left[{{x}_{i+1}}-{{x}_{i}} \right] \\
& =\left[n+1-(i+1)+\frac{1}{i+2}-\left( n+1-i+\frac{1}{1+i} \right) \right] \\
& =\left[-1-\frac{1}{\left( i+1 \right)\left( i+2 \right)} \right] \\
& =-2 \\
\end{align}$ 。
因此，$\displaystyle \sum\limits_{i=1}^{n-1}{\left[{{x}_{i+1}}-{{x}_{i}} \right]=2-2n}$ 。综上，$\displaystyle \sum\limits_{i=1}^{n-1}{\left[{{x}_{i+1}}-{{x}_{i}} \right]}$ 的最大值为 $n-1$，最小值为 $2-2n$ 。

答案解析

由于 $\left[ {{x}_{1}}\right],\left[ {{x}_{2}} \right],\cdots ,\left[ {{x}_{n}} \right]$ 为 $1,2,\cdots ,n$ 的一个排列，因此，对任意 $i=1,2,\cdots ,n$，均有 $1\leqslant {{x}_{i}}<n+1$ $E=\left\{{{u}_{i}}{{u}_{j}},{{v}_{i}}{{v}_{j}},{{u}_{i}}{{v}_{j}}\left| i-j\in \left\{\pm 1,\pm 2,\cdots ,\pm \frac{d-1}{2},\frac{m}{2} \right\}(\bmod m) \right.\right\}$ 。特别地 $1\leqslant {{x}_{1}}<n+1$，$1\leqslant {{x}_{n}}<n+1$，。于是，$-n<{{x}_{n}}-{{x}_{1}}<n$ 。 记 $\displaystyle S=\sum\limits_{i=1}^{n-1}{\left[ {{x}_{i+1}}-{{x}_{i}}\right]}$ 。由于 $\left[ {{x}_{i+1}}-{{x}_{i}} \right]\leqslant{{x}_{i+1}}-{{x}_{i}}$，故 $\displaystyle S\leqslant\sum\limits_{i=1}^{n-1}{({{x}_{i+1}}-{{x}_{i}})={{x}_{n}}-{{x}_{1}}<n}$ 。又 $S$ 为整数，知 $S\leqslant n-1$ 。另一方面，由于 $\left[ {{x}_{i+1}}-{{x}_{i}} \right]>{{x}_{i+1}}-{{x}_{i}}-1$， 故 $\displaystyle S>\sum\limits_{i=1}^{n-1}{({{x}_{i+1}}-{{x}_{i}}-1)}={{x}_{n}}-{{x}_{1}}-(n-1)$ 。又 $S$ 为整数，知 $S\geqslant 2-2n$ 。令 ${{x}_{i}}=i(i=1,2,\cdots ,n)$，得 $\displaystyle \sum\limits_{i=1}^{n-1}{\left[{{x}_{i+1}}-{{x}_{i}} \right]=n-1}$ 。令 ${{x}_{i}}=n+1-i+\frac{1}{1+i}(i=1,2,\cdots,n)$，则对任意的 $i=1,2,\cdots ,n-1$，有 $\begin{align} & \left[{{x}_{i+1}}-{{x}_{i}} \right] \\ & =\left[n+1-(i+1)+\frac{1}{i+2}-\left( n+1-i+\frac{1}{1+i} \right) \right] \\ & =\left[-1-\frac{1}{\left( i+1 \right)\left( i+2 \right)} \right] \\ & =-2 \\ \end{align}$ 。 因此，$\displaystyle \sum\limits_{i=1}^{n-1}{\left[{{x}_{i+1}}-{{x}_{i}} \right]=2-2n}$ 。综上，$\displaystyle \sum\limits_{i=1}^{n-1}{\left[{{x}_{i+1}}-{{x}_{i}} \right]}$ 的最大值为 $n-1$，最小值为 $2-2n$ 。