## 離散情況下中位數最小化差值總和的證明

### 1. 設定

* 假設我們有一個已排序的數列：x₁ ≤ x₂ ≤ ... ≤ xₙ。
* 我們希望找到一個數值 m，使得 Σ |x_i - m|（i 從 1 到 n）最小。
* 令 S(m) = Σ |x_i - m|。

### 2. 考慮兩種情況

* **情況一：n 為奇數**
* 當 n 為奇數時，中位數是 x_k，其中 k = (n + 1) / 2。
* 假設我們將 m 從 x_k 向右移動一個很小的量 ε。
* 那麼，S(m) 的變化量將是：
* ε *（k + 1） - ε * k = ε
* 這代表往右移動會讓總和增加。
* 反之往左移動也會讓總和增加。
* 因此，當 m = x_k 時，S(m) 達到最小值。
* **情況二：n 為偶數**
* 當 n 為偶數時，中位數是 (x_k + x_k+1) / 2，其中 k = n / 2。
* 在此情況下，任何介於 x_k 和 x_k+1 之間的 m 值都會使 S(m) 達到最小值。
* 這是因為，在此範圍內移動 m，增加和減少的差值量相互抵消。

### 3. 結論

* 無論 n 是奇數還是偶數，中位數（或中位數範圍內的任何值）都會使 Σ |xi - m| 達到最小值。

### 簡而言之

* 當我們在已排序的數列中移動 m 時，S(m) 的變化取決於 m 左右兩側的數值個數。
* 中位數平衡了左右兩側的數值個數，因此使 S(m) 最小。