絶対値の和の最小値

方針

解答

⓪ 発想 — どう考え始めるか。 $|x-k|$ の和 $f(x)$ は、下に凸な折れ線になる。$x$ を少し右へ動かすと、$x$ より左にある点への距離は $+1$ ずつ増え、右にある点へは $-1$ ずつ減る。つまり、傾き $=$(左の点の数)$-$(右の点の数)だ。

点は $1,\dots ,100$ の100個(偶数)。$50<x<51$ では左に50個・右に50個で傾き $0$。ここが平らな底で、最小になる。

あとは中央のまわりで、各点への距離を足し上げればよい。

① 最小の位置。 点 $1,\dots ,100$ の中央は50番目と51番目。$50\le x\le 51$ で傾きが $0$ となり、$f$ はそこで一定・最小になる。$x=50$ で計算する。

② 距離を並べる。 $x=50$ から各点への距離は

$$|50-1|,|50-2|,\dots ,|50-100|=49,48,\dots ,1,0,1,2,\dots ,50$$

左側($k=1,\dots ,49$)が $49,48,\dots ,1$。$k=50$ が $0$。右側($k=51,\dots ,100$)が $1,2,\dots ,50$ だ。

③ 和。

$$f(50)=\sum _{j=1}^{49}j+0+\sum _{j=1}^{50}j=\frac{49\cdot 50}{2}+\frac{50\cdot 51}{2}=1225+1275=2500$$

よって最小値は $2500$($50\le x\le 51$)。

まとめ: 絶対値の和は中央値で最小。この一般則を「傾き=左右の個数差」で理解するのが急所だ。偶数個だから中央2点のあいだが平らになる。最小値は、中央からの距離を等差数列の和として計算する。

発展 — 一歩先へ。 「絶対値の和(絶対偏差)を最小にする代表値は中央値」。これはデータの分析で学ぶ事実そのものだ(2乗の和を最小にするのは平均値)。100個の点をデータとみれば、本問はその代表値の話を、折れ線の傾きで証明したことになる。

別解

外側からペアにして足す(直感ルート)。 100本の絶対値を、外側から2本ずつ組にする。

まず両端のペア。$|x-1|+|x-100|$ は「2点 $1,100$ への距離の和」だから、$x$ がその間にあれば最小値 $99$(2点間の距離)。次のペア $|x-2|+|x-99|$ は、間にあれば最小 $97$。以下、$|x-50|+|x-51|$ の最小 $1$ まで、50組できる。

全部足すと

$$f(x)\ge 99+97+95+\cdots +3+1=50^2=2500$$

(奇数を1から99まで足すと $50^2$。)等号は、$x$ が50組すべての「間」にあるとき。いちばんきつい条件は最内のペアの $50\le x\le 51$ で、このとき全ペアが同時に等号になる。よって最小値 $2500$。

「2点への距離の和は、間にいれば2点間の距離」という一番素朴な事実だけで、傾きの議論なしに答えへ届く。$2500=50^2$ という値の正体(奇数の和)まで見えるのがこのルートの収穫だ。