给定实数 $a_{1},a_{2},\ldots,a_{n}$．对每个 $i~(1\leqslant i\leqslant n)$，定义：
$d_{i}=\max\{a_{j}:~1\leqslant j\leqslant i\}-\min\{a_{j}:~i\leqslant j\leqslant n\}$
且令 $d=\max\{d_{i}:~1\leqslant i\leqslant n\}$
（a）证明：对任意实数 $x_{1}\leqslant x_{2}\leqslant\ldots\leqslant x_{n}$，有
$\max\{|x_{i}-a_{i}|:~1\leqslant i\leqslant n\}\geqslant\frac{d}{2}$（$*$）
（b）证明：存在实数 $x_{1}\leqslant x_{2}\leqslant\ldots\leqslant x_{n}$ 使得（$*$）中的等号成立．（新西兰）
$d_{i}=\max\{a_{j}:~1\leqslant j\leqslant i\}-\min\{a_{j}:~i\leqslant j\leqslant n\}$
且令 $d=\max\{d_{i}:~1\leqslant i\leqslant n\}$
（a）证明：对任意实数 $x_{1}\leqslant x_{2}\leqslant\ldots\leqslant x_{n}$，有
$\max\{|x_{i}-a_{i}|:~1\leqslant i\leqslant n\}\geqslant\frac{d}{2}$（$*$）
（b）证明：存在实数 $x_{1}\leqslant x_{2}\leqslant\ldots\leqslant x_{n}$ 使得（$*$）中的等号成立．（新西兰）
【难度】
【出处】
2007年第48届IMO试题
【标注】
【答案】
略
【解析】
（a）设 $d=d_g(1\leqslant g\leqslant n)$
并记 $a_p=\max\{a_j:1\leqslant j\leqslant g\}$，$a_r=\min\{a_j:g\leqslant j\leqslant n\}$
则 $1\leqslant p\leqslant g\leqslant r\leqslant n$ 且 $d=a_p-a_r$．
对任意实数 $x_1\leqslant x_2\leqslant \cdots\leqslant x_n$，注意到
$(a_p-x_p)+(x_r-a_r)=(a_p-a_r)+(x_r-x_p)\geqslant a_p-a_r=d$
所以 $a_p-x_p\geqslant \dfrac{d}{2}$ 或 $x_r-a_r\geqslant \dfrac{d}{2}$，故有
$\max\{|x_i-a_i|:1\leqslant i\leqslant n\}\geqslant\max\{|x_p-a_p|,|x_r-a_r|\}\geqslant\max\{a_p-x_p,x_r-a_r\}\geqslant\dfrac{d}{2}$
（b）定义序列 $\{x_k\}$ 如下：
$x_1=a_1-\dfrac{d}{2},x_k=\max\left\{x_{k-1},a_k-\dfrac{d}{2}\right\},(2\leqslant k\leqslant n)$．
下面证明对这个序列（$*$）取等号．
由 $\{x_k\}$ 的定义知，$\{x_k\}$ 是不减的，且 $x_k-a_k\geqslant -\dfrac{d}{2}$，对所有 $1\leqslant k\leqslant n$ 成立．
下面我们证明：
$x_k-a_k\leqslant\dfrac{d}{2}$ 对所有 $1\leqslant k\leqslant n$ 成立．（1）
对任意 $1\leqslant k\leqslant n$，设 $l\leqslant k$ 是使得 $x_k=x_l$ 的最小下标，则要么 $l=1$，要么 $l\geqslant 2$ 且 $x_l>x_{l-1}$，在这两种情况都有
$x_k=x_l=a_l-\dfrac{d}{2}$（2）
因为 $a_l-a_k\leqslant \max\{a_j:1\leqslant j\leqslant k\}-\min\{a_j:k\leqslant j\leqslant n\}=d_k\leqslant d$
这时由（2）可得
$x_k-a_k=a_l-a_k-\dfrac{d}{2}\leqslant d-\dfrac{d}{2}=\dfrac{d}{2}$
这就是（1）．这样就得到
$-\dfrac{d}{2}\leqslant x_k-a_k\leqslant\dfrac{d}{2}$
对所有 $1\leqslant k\leqslant n$ 成立，故
$\max\{|x_i-a_i|:1\leqslant i\leqslant n\}\leqslant \dfrac{d}{2}$
再由（a）知 $\{x_k\}$ 确使得（$*$）取等号．
（b）的另解：
对每个 $i(1\leqslant i\leqslant n)$，令 $M_i=\max\{a_j:1\leqslant j\leqslant i\},m_i=\min\{a_j:i\leqslant j\leqslant\}$，则
$M_i=\max\{a_1,\cdots,a_i\}\leqslant \max\{a_1,\cdots,a_i,a_{i+1}\}=M_{i+1}$
$m_i=\min\{a_i,a_{i+1}\cdots,a_n\}\leqslant \min\{a_{i+1},\cdots,a_n
\}=m_{i+1}$
这说明序列 $\{M_i\}$ 和 $\{m_i\}$ 都是不减的，且由它的定义知 $m_i\leqslant a_i\leqslant M_i$．
现令 $x_i=\dfrac{M_i+m_i}{2}$，由 $d_i=M_i-m_i$ 可得
$-\dfrac{d}{2}=\dfrac{m_i-M_i}{2}=x_i-M_i\leqslant x_i-a_i\leqslant x_i-m_i=\dfrac{M_i-m_i}{2}=\dfrac{d_i}{2}$
因此 $\max\{|x_i-a_i|:1\leqslant i\leqslant n\}\leqslant \max\left\{\dfrac{d_i}{2}:1\leqslant i\leqslant n\right\}=\dfrac{d}{2}$
再由（a）的结论知，$\{x_k\}$ 使得（$*$）中的等号成立．
并记 $a_p=\max\{a_j:1\leqslant j\leqslant g\}$，$a_r=\min\{a_j:g\leqslant j\leqslant n\}$
则 $1\leqslant p\leqslant g\leqslant r\leqslant n$ 且 $d=a_p-a_r$．
对任意实数 $x_1\leqslant x_2\leqslant \cdots\leqslant x_n$，注意到
$(a_p-x_p)+(x_r-a_r)=(a_p-a_r)+(x_r-x_p)\geqslant a_p-a_r=d$
所以 $a_p-x_p\geqslant \dfrac{d}{2}$ 或 $x_r-a_r\geqslant \dfrac{d}{2}$，故有
$\max\{|x_i-a_i|:1\leqslant i\leqslant n\}\geqslant\max\{|x_p-a_p|,|x_r-a_r|\}\geqslant\max\{a_p-x_p,x_r-a_r\}\geqslant\dfrac{d}{2}$
（b）定义序列 $\{x_k\}$ 如下：
$x_1=a_1-\dfrac{d}{2},x_k=\max\left\{x_{k-1},a_k-\dfrac{d}{2}\right\},(2\leqslant k\leqslant n)$．
下面证明对这个序列（$*$）取等号．
由 $\{x_k\}$ 的定义知，$\{x_k\}$ 是不减的，且 $x_k-a_k\geqslant -\dfrac{d}{2}$，对所有 $1\leqslant k\leqslant n$ 成立．
下面我们证明：
$x_k-a_k\leqslant\dfrac{d}{2}$ 对所有 $1\leqslant k\leqslant n$ 成立．（1）
对任意 $1\leqslant k\leqslant n$，设 $l\leqslant k$ 是使得 $x_k=x_l$ 的最小下标，则要么 $l=1$，要么 $l\geqslant 2$ 且 $x_l>x_{l-1}$，在这两种情况都有
$x_k=x_l=a_l-\dfrac{d}{2}$（2）
因为 $a_l-a_k\leqslant \max\{a_j:1\leqslant j\leqslant k\}-\min\{a_j:k\leqslant j\leqslant n\}=d_k\leqslant d$
这时由（2）可得
$x_k-a_k=a_l-a_k-\dfrac{d}{2}\leqslant d-\dfrac{d}{2}=\dfrac{d}{2}$
这就是（1）．这样就得到
$-\dfrac{d}{2}\leqslant x_k-a_k\leqslant\dfrac{d}{2}$
对所有 $1\leqslant k\leqslant n$ 成立，故
$\max\{|x_i-a_i|:1\leqslant i\leqslant n\}\leqslant \dfrac{d}{2}$
再由（a）知 $\{x_k\}$ 确使得（$*$）取等号．
（b）的另解：
对每个 $i(1\leqslant i\leqslant n)$，令 $M_i=\max\{a_j:1\leqslant j\leqslant i\},m_i=\min\{a_j:i\leqslant j\leqslant\}$，则
$M_i=\max\{a_1,\cdots,a_i\}\leqslant \max\{a_1,\cdots,a_i,a_{i+1}\}=M_{i+1}$
$m_i=\min\{a_i,a_{i+1}\cdots,a_n\}\leqslant \min\{a_{i+1},\cdots,a_n
\}=m_{i+1}$
这说明序列 $\{M_i\}$ 和 $\{m_i\}$ 都是不减的，且由它的定义知 $m_i\leqslant a_i\leqslant M_i$．
现令 $x_i=\dfrac{M_i+m_i}{2}$，由 $d_i=M_i-m_i$ 可得
$-\dfrac{d}{2}=\dfrac{m_i-M_i}{2}=x_i-M_i\leqslant x_i-a_i\leqslant x_i-m_i=\dfrac{M_i-m_i}{2}=\dfrac{d_i}{2}$
因此 $\max\{|x_i-a_i|:1\leqslant i\leqslant n\}\leqslant \max\left\{\dfrac{d_i}{2}:1\leqslant i\leqslant n\right\}=\dfrac{d}{2}$
再由（a）的结论知，$\{x_k\}$ 使得（$*$）中的等号成立．
答案
解析
备注
