Re: [請益] 有沒有人記得
※ 引述《west1996 (焦了六年變脆了)》之銘言：
: sum |Xi-a| 最小值發生在 a=median{Xi} 要怎麼證？
: i
: 我要離散型版本的~
: 會的阿龍請吃韓江!!
最小值的解不唯一唷 median 只是其中一個解
可以作為高中數學歸納法的題目
先給的 Lemma
Lemma: Suppose X < Y and f(c) = |X-c| + |Y-c|, then we have
f(c) >= f(m) for all m with X <= m <= Y and for all c in R
(在 X 跟 Y 中間的值都是最小值的解)
Proof: 略... 太容易了
開始數學歸納法
n = 1 時，顯然成立
n = 2 時，按照 Lemma 中位數顯然是一個最小值的解
假設 n = k, n = k + 1 時都成立
當 n = k + 2 時
符號採用排序好的 X_(1) <= X_(2) <= ... <= X_(k+1) <= X_(k+2)
先不考慮最大值和最小值，從 X_(2) 到 X_(k+1) 共有 k 個
令 g(c) = |X_(2) - c| + ... + |X_(k+1) - c|, a = median{Xi; 2 <= i <= k+1}
由歸納假設 (n=k) X_(2) ~ X_(k+1) 的中位數是最小解，即
g(c) >= g(a) for all c in R --- (1)
令 f(c) = |X_(1) - c| + |X_(k+2) - c|
顯然 X_(1) < a < X_(k+2) 利用 Lemma 可得
f(c) >= f(a) for all c in R --- (2)
(1) + (2) 可得
sum |Xi-c| = g(c) + f(c) >= g(a) + f(a) for all c in R
故 a 是最小值的一個解
注意到 a = median{Xi; 2 <= i <= k+1} = median{Xi; 1 <= i <= k+2}
補充：在證明中，似乎沒用到歸納假設 n = k+1 部分，
但事實上 X_(1) 和 X_(k+2) 的 "存在性" 是必須，
這部份就有用到 n = k+1 ，懶得寫的很完整，意思大概是這樣
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.196.42
推
03/26 23:58, , 1F
03/26 23:58, 1F
→
03/27 00:00, , 2F
03/27 00:00, 2F
→
03/27 00:01, , 3F
03/27 00:01, 3F
→
03/27 00:02, , 4F
03/27 00:02, 4F
→
03/27 00:02, , 5F
03/27 00:02, 5F
→
03/27 00:03, , 6F
03/27 00:03, 6F
→
03/27 00:03, , 7F
03/27 00:03, 7F
1. 以 Lemma 舉例來說：假設 X=1, Y=3, 則 f(c) = |1-c| + |3-c|
只要 1<=c<=3 , 就有 f(c) = c-1 + 3-c = 2 是最小值
中位數 "2" 只是其中一個解。
2. Lemma 只用兩個數 (X,Y)，而不用三個數 (X,Y,Z) 是為後面的歸納法作準備的
Lemma 說的是 n = 2 的情況，所有最小值的範圍，中位數只是其中一個解
3. 中位數有個特徵：將數列 (個數必須大於3; n>=3) 中的最大值和最小值同時抽去，
其中位數不變，也是就說
a = median{Xi; 2 <= i <= k+1} = median{Xi; 1 <= i <= k+2}
可由中位數的定義證明，證明略
4. 歸納法中的 a 是被固定的，並沒有重取的問題，一開始 a 就被定義為
a = median{Xi; 2 <= i <= k+1}
這個 a 符合歸納假設，故有 (1)
同時 a 也符合X_(1) < a < X_(k+2)，故可引用 Lemma，故有 (2)
注意！我並沒有說 a 是 X_(1) 和 X_(k+2) 的中位數
事實上 a 沒有必要是 X_(1) 和 X_(k+2) 的中位數，Lemma一樣可使用
這就是我 Lemma 為什麼要那樣寫的原因，
這樣即使 a 不是 X_(1) 和 X_(k+2) 的中位數，亦會有 (2)
5. 可以一步一步來思考
n = 1： |X_(1)-c| 之最小值解是 a = X_(1) 中位數
n = 2： |X_(1)-c| + |X_(2)-c| 其中一個最小值解是中位數
n = 3： |X_(1)-c| + |X_(2)-c| + |X_(3)-c|
先不看最小值 X_(1) 和最大值 X_(3)
按照 n=1， X_(2)的中位數 a 是 |X_(2)-c| 最小值的解
同時這個 a 可引用 Lemma，亦是 |X_(1)-c| + |X_(3)-c| 最小值的解
故 |X_(1)-c| + |X_(2)-c| + |X_(3)-c| 其中一個最小值解是 a
最後利用中位數的性質，a 亦是 X_(1) ~ X_(3) 的中位數
n = 4, 5, 6....
不斷重覆上面步驟
步驟 1： 將原本數列拿去最大值和最小值，定義 a 是新數列的中位數
步驟 2： 利用歸納假設，a 是新數列的最小值之解
步驟 3： a 與最大值和最小值的關係滿足 Lemma，可使用 Lemma
步驟 4： 由步驟 2 和步驟 3 ，可知 a 是原數列的最小值之解
步驟 5： 最後說明 a 其實也是原數列的中位數
※ 編輯: zhixiangJ 來自: 118.169.192.37 (03/27 08:06)
推
03/27 08:09, , 8F
03/27 08:09, 8F
→
03/27 08:10, , 9F
03/27 08:10, 9F
→
03/27 10:48, , 10F
03/27 10:48, 10F
→
03/27 10:49, , 11F
03/27 10:49, 11F
推
03/27 13:52, , 12F
03/27 13:52, 12F
推
03/27 18:03, , 13F
03/27 18:03, 13F
推
03/27 18:13, , 14F
03/27 18:13, 14F
推
03/28 17:16, , 15F
03/28 17:16, 15F
推
03/28 23:06, , 16F
03/28 23:06, 16F
推
03/30 01:33, , 17F
03/30 01:33, 17F
推
03/30 02:20, , 18F
03/30 02:20, 18F
推
03/30 11:50, , 19F
03/30 11:50, 19F
→
03/30 21:52, , 20F
03/30 21:52, 20F
推
03/30 22:20, , 21F
03/30 22:20, 21F
討論串 (同標題文章)