解説

方針・初手

絶対値の和の最小値を求める問題である。$n$ の変化に伴う値の増減を調べるために、隣り合う項の差分 $S_{n+1} - S_n$ を計算して数列の単調性を判定する方針が簡明である。 また、絶対値 $|x-a|$ が数直線上の点 $x$ と点 $a$ との距離を表すことを利用し、グラフの形状や三角不等式から直感的に最小値を与える $n$ の範囲を絞り込む方針も有効である。

解法1

関数としてではなく、数列 $S_n$ の増減を調べる。

$$ S_n = \sum_{k=1}^{100} |n-k| $$

とする。$n \le 0$ のときは $n$ が増加すると各 $|n-k| = k-n$ が減少するため $S_n$ も単調に減少する。また $n \ge 100$ のときは各 $|n-k| = n-k$ となり $S_n$ は単調に増加する。したがって、最小値は $1 \le n \le 100$ の範囲で探せばよい。 $1 \le n \le 99$ の整数 $n$ について、隣り合う項の差 $S_{n+1} - S_n$ を考える。

$$ \begin{aligned} S_{n+1} - S_n &= \sum_{k=1}^{100} |n+1-k| - \sum_{k=1}^{100} |n-k| \\ &= \sum_{k=1}^{100} ( |n+1-k| - |n-k| ) \end{aligned} $$

ここで、$k$ の範囲によって絶対値の中身の符号が変わるため、和を分割する。

**(i) $1 \le k \le n$ のとき**

$n+1-k > 0$ かつ $n-k \ge 0$ であるから、

$$ |n+1-k| - |n-k| = (n+1-k) - (n-k) = 1 $$

**(ii) $n+1 \le k \le 100$ のとき**

$n+1-k \le 0$ かつ $n-k < 0$ であるから、

$$ |n+1-k| - |n-k| = -(n+1-k) - \{ -(n-k) \} = -1 $$

これらを差分の式に代入する。

$$ \begin{aligned} S_{n+1} - S_n &= \sum_{k=1}^{n} 1 + \sum_{k=n+1}^{100} (-1) \\ &= n \cdot 1 + (100-n) \cdot (-1) \\ &= 2n - 100 \end{aligned} $$

この結果から、$S_n$ の増減は以下のようになる。

• $n \le 49$ のとき、$2n - 100 < 0$ より $S_{n+1} < S_n$ （単調減少）
• $n = 50$ のとき、$2n - 100 = 0$ より $S_{51} = S_{50}$
• $n \ge 51$ のとき、$2n - 100 > 0$ より $S_{n+1} > S_n$ （単調増加）

したがって、$S_n$ は $n=50, 51$ のときに最小値をとる。 その最小値は $n=50$ を代入して計算できる。

$$ \begin{aligned} S_{50} &= \sum_{k=1}^{100} |50-k| \\ &= \sum_{k=1}^{50} (50-k) + \sum_{k=51}^{100} (k-50) \\ &= (49 + 48 + \dots + 1 + 0) + (1 + 2 + \dots + 50) \\ &= \frac{1}{2} \cdot 49 \cdot 50 + \frac{1}{2} \cdot 50 \cdot 51 \\ &= 1225 + 1275 \\ &= 2500 \end{aligned} $$

解法2

絶対値の幾何学的意味（数直線上の距離）を利用する。 実数 $x$ に対して、関数 $f(x)$ を次のように定める。

$$ f(x) = \sum_{k=1}^{100} |x-k| $$

$|x-k|$ は数直線上の点 $x$ と点 $k$ との距離を表す。 ここで、定点 $1, 2, \dots, 100$ を両端から順にペアリングして距離の和を評価する。自然数 $m \ (1 \le m \le 50)$ に対して、点 $m$ と点 $101-m$ のペアを考えると、三角不等式より以下の関係が成り立つ。

$$ \begin{aligned} |x-m| + |x-(101-m)| &= |x-m| + |101-m-x| \\ &\ge |(x-m) + (101-m-x)| \\ &= |101-2m| \\ &= 101-2m \end{aligned} $$

等号が成立するのは、点 $x$ が点 $m$ と点 $101-m$ の間にあるとき、すなわち $m \le x \le 101-m$ のときである。 これをすべての $m=1, 2, \dots, 50$ について足し合わせると、次のように評価できる。

$$ \begin{aligned} f(x) &= \sum_{m=1}^{50} \{ |x-m| + |x-(101-m)| \} \\ &\ge \sum_{m=1}^{50} (101-2m) \end{aligned} $$

この等号がすべての $m$ で同時に成立する条件は、すべての $m \ (1 \le m \le 50)$ に対して $m \le x \le 101-m$ が成り立つことである。 $m$ が最大値 $50$ をとるとき、区間は最も狭くなり $50 \le x \le 51$ となる。このとき、他のすべての $m$ に対する条件も満たされる。 本問において $n$ は整数であるから、$50 \le n \le 51$ を満たす整数は $n=50, 51$ のみである。 このとき最小値となり、その値は次のように計算できる。

$$ \begin{aligned} \sum_{m=1}^{50} (101-2m) &= \sum_{m=1}^{50} 101 - 2 \sum_{m=1}^{50} m \\ &= 101 \cdot 50 - 2 \cdot \frac{1}{2} \cdot 50 \cdot 51 \\ &= 5050 - 2550 \\ &= 2500 \end{aligned} $$

解説

関数 $f(x) = \sum_{k=1}^{N} |x-x_k|$ の最小値は、データ $x_1, x_2, \dots, x_N$ の「中央値（メジアン）」でとるという統計における有名な性質を背景とした問題である。 データ数が奇数の場合は中央値が1点に定まるためグラフは折れ線となり谷が1つになるが、本問のようにデータ数が偶数（100個）の場合は、中央値が2つの値の間の区間（$50 \le x \le 51$）となり、グラフの底が平らになるのが特徴である。 解法1はこれを数式で厳密に示したものであり、解法2は幾何学的な意味から直感的にアプローチしたものである。どちらの解法も標準的なので習得しておきたい。

答え

最小値: $2500$

そのときの $n$ の値: $n = 50, 51$