トップ› 京都大学› 1961年› 理系第5問

京都大学 1961年理系第5問解説

方針・初手

絶対値の和 $S$ は、数直線上において点 $n$ と各点 $1, 2, \dots, 100$ との距離の総和を表す。この意味に着目して両端からペアを作るか、あるいは隣接する整数における値の差 $S(n+1) - S(n)$ を計算して増減を調べる。

解法1

$S$ の各項を数直線上における両端からペアになるように組み合わせて、以下のように変形する。

$$ S = \sum_{k=1}^{50} ( |n-k| + |n-(101-k)| ) $$

絶対値の性質（または数直線上の距離の意味）から、任意の実数 $n$ と定数 $a < b$ について、以下の三角不等式が成り立つ。

$$ |n-a| + |n-b| \geqq b - a $$

等号が成立するのは、$a \leqq n \leqq b$ のときである。この性質を $a = k, b = 101-k$ （$k=1, 2, \dots, 50$）として各ペアに適用すると、次が成り立つ。

$$ |n-k| + |n-(101-k)| \geqq (101-k) - k = 101 - 2k $$

等号成立条件は $k \leqq n \leqq 101-k$ である。したがって、$S$ 全体については辺々を足し合わせて以下の不等式が成り立つ。

$$ S \geqq \sum_{k=1}^{50} (101 - 2k) $$

この不等式の等号が成立するのは、すべての $k=1, 2, \dots, 50$ について $k \leqq n \leqq 101-k$ が同時に成り立つときである。これを満たすためには、最も範囲が狭くなる $k=50$ のときの条件を満たせばよく、その条件は $50 \leqq n \leqq 51$ となる。

問題の条件より $n$ は整数であるから、この条件を満たすのは $n = 50, 51$ のときである。このとき $S$ は最小となり、その最小値は次のように計算できる。

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

解法2

隣接する整数における $S$ の値の差分を考える。 $S(n)$ を以下のように定義する。

$$ S(n) = \sum_{k=1}^{100} |n-k| $$

$n$ が 1 増えたときの変化量 $S(n+1) - S(n)$ を計算して増減を調べる。

$$ S(n+1) - S(n) = \sum_{k=1}^{100} ( |n+1-k| - |n-k| ) $$

$k \leqq n$ を満たす $k$ に対しては、数直線上で $k, n, n+1$ の順に並ぶため、点 $n$ から $n+1$ へ移動すると距離は $1$ 増加する。すなわち $|n+1-k| - |n-k| = 1$ となる。一方、$k \geqq n+1$ を満たす $k$ に対しては、数直線上で $n, n+1, k$ の順に並ぶため、点 $n$ から $n+1$ へ移動すると距離は $1$ 減少する。すなわち $|n+1-k| - |n-k| = -1$ となる。

(i)

$1 \leqq n \leqq 99$ のとき $1$ から $100$ までの整数のうち、$n$ 以下のものは $n$ 個、$n+1$ 以上のものは $100-n$ 個ある。したがって、

$$ \begin{aligned} S(n+1) - S(n) &= n \times 1 + (100 - n) \times (-1) \\ &= 2n - 100 \end{aligned} $$

(ii)

$n \leqq 0$ のときすべての $k=1, 2, \dots, 100$ に対して $k \geqq n+1$ となるため、

$$ S(n+1) - S(n) = 100 \times (-1) = -100 < 0 $$

(iii)

$n \geqq 100$ のときすべての $k=1, 2, \dots, 100$ に対して $k \leqq n$ となるため、

$$ S(n+1) - S(n) = 100 \times 1 = 100 > 0 $$

以上より、各整数 $n$ における増減は以下のようになる。

$n \leqq 49$ のとき、$2n - 100 < 0$ より $S(n+1) - S(n) < 0$ （単調減少）
$n = 50$ のとき、$2 \times 50 - 100 = 0$ より $S(51) - S(50) = 0$
$n \geqq 51$ のとき、$2n - 100 > 0$ より $S(n+1) - S(n) > 0$ （単調増加）

したがって、$S(n)$ は $n \leqq 50$ で減少し、$n \geqq 51$ で増加するため、$n=50$ と $n=51$ のときに最小値をとる。このときの最小値は、

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

解説

数直線上の複数の点からの距離の和を最小化する問題は、統計学における「中央値」の性質としてよく知られている。データが $x_1, x_2, \dots, x_m$ のとき、関数 $f(x) = \sum |x - x_i|$ は $x$ がこれらの中央値と一致するときに最小となる。本問ではデータが $1, 2, \dots, 100$ と偶数個あるため、中央値は50番目と51番目の値に挟まれた区間、つまり $50 \leqq x \leqq 51$ の範囲すべてとなる。論述の手段としては、解法1のように両端からペアリングして三角不等式を利用するか、解法2のように階差数列を計算して増減を明確に示すアプローチが標準的であり、論理の飛躍なく解答を構築できる。