Re: [代數] 級數的不等式證明

[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的性質？
: 感謝回答～

令
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.1726540934.A.519.html
→ musicbox810 : 請問m大S_k \ S'_k的\是什麼符號？
推 LPH66       : 集合差, 在前者但不在後者之中的元素
→ LPH66       : 有人寫減, 也有人寫反斜線
→ musicbox810 : 謝謝L大的解釋
→ musicbox810 : 不懂為什麼max(P_k) ≦ min(Q_k)會成立？
以c(A)表示A的補集 ( 宇集是 {a_1, ..., a_n} )

P_k = S_k ∩ c(S'_k) => P_k 包含於S_k
Q_k = S'_k ∩ c(S_k) => Q_k 包含於c(S_k)

S_k 其實就是 {a_1,...,a_k}, 而c(S_k)就是 { a_(k+1), ... ,a_n }

因此對所有k, max(S_k) ≦ min(c(S_k))
因此 max(P_k) ≦ max(S_k) ≦ min(c(S_k)) ≦ min(Q_k)


---------------------------------------------------------


換一個方式想

給定任意 k 和 σ

若 a_σ(1) ~ a_σ(k) 中有m個數大於 a_k (0<=m<=k)

就表示 a_σ(k+1) ~ a_σ(n) 中有m個數小於等於 a_k

現在進行以下操作:

把 前面m個大於a_k的數 跟 後面m個小於a_k的數一對一對調

對調之後 a_σ(1) ~ a_σ(k) 的和一定是變小

(當m=0時不做任何事,所以不變)

也就是對調後前k項的和 A''_k <= A'_k

而對調後 a_σ(1) ~ a_σ(k) 全部都小於等於 a_k

因此對調後的前k項就是 a_1 ~ a_k 的permutation

因此 A''_k = A_k

就得到 A_k <= A'_k


推 TimcApple   : 設 Sc 為 >k 的元素, 若 P, Q 非空則
→ TimcApple   : maxP <= maxS = k < k+1 = minSc <= minQ
→ mantour     : P_k裡面全部都是原數列的前k項， Q_k裡面全部都是k
→ mantour     : +1之後的項
→ mantour     : 所以P_k的任何一個元素都比Q_k的任何一個元素小
※ 編輯: mantour (220.137.14.92 臺灣), 09/17/2024 20:10:09
→ mantour     : 阿 要註明如果有重複項要當大小相同的相異元素
推 Vulpix      : 如果把排序不等式當作已知來用，第二個數列用1跟0做
→ Vulpix      : 就可以了。