作者mantour (朱子)
看板Math
標題Re: [代數] 級數的不等式證明
時間Tue Sep 17 10:42:11 2024
※ 引述《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://webptt.com/m.aspx?n=bbs/Math/M.1726540934.A.519.html
1F：→ musicbox810 : 請問m大S_k \ S'_k的\是什麼符號？ 09/17 12:15
2F：推 LPH66 : 集合差, 在前者但不在後者之中的元素 09/17 12:23
3F：→ LPH66 : 有人寫減, 也有人寫反斜線 09/17 12:23
4F：→ musicbox810 : 謝謝L大的解釋 09/17 12:47
5F：→ musicbox810 : 不懂為什麼max(P_k) ≦ min(Q_k)會成立？ 09/17 13:15
以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
6F：推 TimcApple : 設 Sc 為 >k 的元素, 若 P, Q 非空則 09/17 14:31
7F：→ TimcApple : maxP <= maxS = k < k+1 = minSc <= minQ 09/17 14:31
8F：→ mantour : P_k裡面全部都是原數列的前k項， Q_k裡面全部都是k 09/17 17:11
9F：→ mantour : +1之後的項 09/17 17:11
10F：→ mantour : 所以P_k的任何一個元素都比Q_k的任何一個元素小 09/17 17:12
※ 編輯: mantour (220.137.14.92 臺灣), 09/17/2024 20:10:09
11F：→ mantour : 阿 要註明如果有重複項要當大小相同的相異元素 09/19 22:20
12F：推 Vulpix : 如果把排序不等式當作已知來用，第二個數列用1跟0做 09/22 00:21
13F：→ Vulpix : 就可以了。 09/22 00:22