※ 引述《mantour (朱子)》之銘言：
: ※ 引述《Lanjaja ()》之銘言：
: : 想問一道不等式證明：
: : 設a_1 ≦ a_2 ≦ ... ≦ a_n，a_i不限正負。
: : 定義A_k =Σ_(i=1 to k) a_i
: : A'_k = Σ_(i=1 to k) a_σ(i)
: : σ(i)是i的置換permutation
: : 證明對所有的k=1~n，A_k≦A'_k都成立。
: : 請問強者應該要怎麼證明這個A_k的性質？
: : 感謝回答～
數學歸納法:
(1) 對任意 σ, k=1時
因為 a_1 ≦ a_2 ≦ ... ≦ a_n
所以 A_1 = a_1 ≦ a_σ(1) = A'_1
(2) 假設對任意 σ, k=j 時 (1<j<n), A_j ≦ A'_j 都成立
若 σ(j+1) >= j+1
則 a_σ(j+1) >= a_(j+1)
A_(j+1) = A_j + a_(j+1)
<= A_j + a_σ(j+1)
<= A'_j + a_σ(j+1) = A'_(j+1)
若 σ(j+1) <= j
則 存在 1<= m <= j 使得 σ(m) >= j+1
令 σ'(i) = { σ(i), if i不等於 m, j+1
σ(j+1), if i=m
σ(m), if i=j+1
(也就是第m項和第j+1項對調, 對調後前j+1項的和不變)
A''_k = Σ_(i=1 to k) a_σ'(i)
則 A'_(j+1) = A''_(j+1)
= A''_j + a_σ(m)
>= A_j + a_σ(m)
>= A_j + a_(j+1)
= A_(j+1)
因此 k=j+1時也成立
由(1), (2) 及數學歸納法得證 k=1~n時都成立
: 令
: S_k={a_i, i=1~k}
: S'_k={a_σ(i), i=1~k}
: P_k= S_k \ S'_k
: Q_k= S'_k \ S_k
: 則
: sum(S_k) - sum(S'_k) = sum(P_k) - sum(Q_k)
: n(P_k) = n(Q_k) = k - n(S_k∩S'_k)
: 對所有 x 屬於 P_k 且 y屬於Q_k , x≦y
: 因此 sum(P_k) ≦ n(P_k)*max(P_k) ≦ n(Q_k)*min(Q_k) ≦ sum(Q_k)
: => sum(S_k) ≦ sum(S'_k)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.14.92 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1726576419.A.01B.html
※ 編輯: mantour (220.137.14.92 臺灣), 09/17/2024 20:39:22
※ 編輯: mantour (220.137.14.92 臺灣), 09/17/2024 20:42:05