绝对值最值

题目

记 $(x_1,x_2,\ldots,x_{20})$ 是 $(1,2,3,\ldots,20)$ 的一个排列,并记
$$
S=\sum_{i=1}^{20}\vert x_i-i\vert
$$
求 $S$ 的最值.

分析及解答

首先最小值我相信大家都能看出来,是零.只需要取
$$
x_i=i
$$
即可,并且结合 $S\geq 0$ 即证.

所以关键问题在于最大值的求解.由于 $x_i$ 与 $i$ 的关系难以直接判断,造成难以继续下一步处理,其实大家应该也能猜到,其实我们可以有一种贪心的策略.什么意思呢,就是我按 $1,2,\ldots,20$ 的顺序依次确定 $x_i$,而我每次取的时候都让 $\vert x_i-i\vert$ 尽可能的大,也就是这样:

  • $i=1$ 时,取 $x_1=20$,则使得 $\vert x_1-1\vert$ 最大化;

  • $i=2$ 时,由于这个时候 $20$ 已经被取过,于是取 $x_2=19$ ;

  • $x_3=18$;

  • $\ldots$

  • $i=8$ 时,这时候有点问题,因为按上面的规律理应当取 $x_8=13$,但是很明显有
    $$
    \vert 13-8\vert=5<\vert 1-8\vert
    $$
    也就是应当取 $x_8=1$;

  • 接下来则都遵循 $x_i=i-7$,换言之 $\vert x_i-i\vert=7$.

那么取完之后可以计算一下结果:

$$ \begin{align*} S&=\sum_{i=1}^{7}\vert x_i-i\vert+\sum_{i=8}^{20}\vert x_i-i\vert\\ &=\sum_{i=1}^{7}((21-i)-i)+7\times (20-8+1)\\ &=21\times 7-7\times 8+7\times 13\\ &=182 \end{align*} $$

但是这样好像有点问题,也的确证明不了是最大值,因为虽然越前面越大,但是后面好像却变小了.并且注意,这个方法还挺繁琐,竟然还要分类讨论.其实我们可以很容易联想到另外一个猜测,就是 $(x_1,x_2,\ldots,x_{20})$ 刚好和原序列反过来,也就是
$$
(20,19,\ldots,2,1)
$$
那先算一下答案,由对称性:

$$ \begin{align*} S&=2\sum_{i=1}^{10}\vert x_i-i\vert\\ &=2(\sum_{i=11}^{20}i-\sum_{i=1}^{10}i)\\ &=21\times 10-11\times 10\\ &=200 \end{align*} $$

一看就会觉得这个答案靠谱很多.那到底是不是最大值呢?

首先我们要说明这个问题的第一个障碍就是绝对值,为了方便观察,可以进行如下转换,注意到:

$$ \vert a-b\vert=\max\{a,b\}-\min\{a,b\} $$

意思就是说在 $\vert x_i-i\vert$ 中,$x_i$ 必定会作为 $\max$ 或者是 $\min$,剩下的就是 $i$.这样处理可以给我们一个全局的思考方向.因为 $x_i$ 还有 $i$ 其实都是 $1-20$ 之间的某一个数,也就是说对于任何一个 $i\in {1,2,\ldots,20}$,必定在 $\max$ 或 $\min$ 中出现两次.所以要最大化,只需要 $i>10$ 时全部取到 $\max$,$i<11$ 时全部取到 $\min$.也就是
$$
\begin{align*}
S&\leq2(\sum_{i=11}^{20}i-\sum_{i=1}^{10}i)\
&=200
\end{align*}
$$
故最大值就是 $200$.

题外话

实际上一旦发现这点后可以知道

当 $i<11$ 时,取 $x_i\in\{11,12,\ldots,20\}$; 当 $i>10$ 时,取 $x_i\in\{1,2,\ldots,10\}$.

啥意思?就是有 $(10!)^2$ 种取法.

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×