Top

---

最小値関数 min・最大値関数 max に関する加法定理

変数が 2個の場合

最小値を返す関数 min, 最大値を返す関数 max には次の法則が成り立つ。
　min (x₁ + x₂ , y₁ + y₂) ≧ min (x₁ , y₁) + min (x₂ , y₂)
　max (x₁ + x₂ , y₁ + y₂) ≦ max (x₁ , y₁) + max (x₂ , y₂)

証明

min (x₁ + x₂ , y₁ + y₂) ≧ min (x₁ , y₁) + min (x₂ , y₂) について証明する。

　(左辺) = s₁ = min (x₁ + x₂ , y₁ + y₂)
　(右辺) = s₂ = min (x₁ , y₁) + min (x₂ , y₂)
と置く。x₁, y₁ と x₂, y₂ の大小関係で場合分けする。

	x1 ≦ y1 の場合	x1 ＞ y1 の場合
x2 ≦ y2 の場合	x1 + x2 ≦ y1 + y2 が成り立つので、 s1 = min (x1 + x2 , y1 + y2) = x1 + x2 s2 = min (x1 , y1) + min (x2 , y2) = x1 + x2 よって、s1 = s2	s2 = min (x1 , y1) + min (x2 , y2) = x2 + y1 さらに場合分けする。 ① x1 + x2 ≦ y1 + y2 の場合 　s1 = min (x1 + x2 , y1 + y2) = x1 + x2 　s1 - s2 = x1 + x2 - (x2 + y1) = x1 - y1 ＞ 0 　よって、s1 ＞ s2 ②x1 + x2 ＞ y1 + y2 の場合 　s1 = min (x1 + x2 , y1 + y2) = y1 + y2 　s1 - s2 = y1 + y2 - (x2 + y1) = y2 - x2 ≧ 0 　よって、s1 ≧ s2
x2 ＞ y2 の場合	s2 = min (x1 , y1) + min (x2 , y2) = x1 + y2 さらに場合分けする。 ① x1 + x2 ≦ y1 + y2 の場合 　s1 = min (x1 + x2 , y1 + y2) = x1 + x2 　s1 - s2 = x1 + x2 - (x1 + y2) = x2 - y2 ＞ 0 　よって、s1 ＞ s2 ②x1 + x2 ＞ y1 + y2 の場合 　s1 = min (x1 + x2 , y1 + y2) = y1 + y2 　s1 - s2 = y1 + y2 - (x1 + y2) = y1 - x1 ≧ 0 　よって、s1 ≧ s2	x1 + x2 ＞ y1 + y2 が成り立つので、 s1 = min (x1 + x2 , y1 + y2) = y1 + y2 s2 = min (x1 , y1) + min (x2 , y2) = y1 + y2 よって、s1 = s2

よって、包括すると s₁ ≧ s₂ が成り立つ。

一般化　変数が n個の場合

　min (Σ x_i , Σ y_i) ≧ Σ min (x_i , y_i)
　max (Σ x_i , Σ y_i) ≦ Σ max (x_i , y_i)

証明は 変数が 2個の場合を用いて漸化的にできる。