難數 [證明類高手請入]

排序原理 :

順序和 >= 亂序和 >= 逆序和

對兩個數列 :
a1>=a2>=a3>=...>=an
b1>=b2>=b3>=...>=bn

a1b1 + a2b2 + a3b3 + ...+anbn>=

a1bj1 + a2bj2 + a3bj3 + ...anbjn>=

a1bn + a2b(n-1) + a3b(n-2) + ... + anb1

1)先證一個引理 :

對於 am <= an , bm <= bn ,有 (am bm + an bn) >= (am bn + an bm)

證: (am bm + an bn) - (am bn + an bm)
= am(bm - bn) + an(bn - bm)
= am(bm - bn) - an(bm - bn)
= (am - an)(bm - bn)>=0 (當am = an 或 bm = bn 時等號成立)

2)利用局部調整 :

對一個亂序和 : a1bj1 + a2bj2 + a3bj3 +...+ akb1 +...+ anbjn....(*)

利用引理 , (*) < = a1 b1 + a2bj2 + a3bj3 +...+ ak bj1 +...+ anbjn

重複此步驟,對 a2 a3 a4...an進行上述調整 ,在至多 n-1 步內 ,
必得到 :

(*) < = a1b1 + a2b2 + a3b3 +...+ anbn
此即順序和>=亂序和,當a1=a2=...=an 或
b1=b2=...bn時等式成立。

同理,把以上過程逆轉,在n-1步內即可證明
(*) < = a1bn + a2b(n-1) + ... + anb1 ,
當a1=a2=...=an 或
b1=b2=...bn時等式成立。

綜合以上即得排序不等式 :

a1b1+a2b2+....+anbn

>=a1bj1+a2bbj2+...+anbjn

>=a1bn+a2bn-1+...+anb1




2009-10-30 19:46:37 補充：
同理,把以上過程逆轉,在n-1步內即可證明
(*) <= a1bn + a2b(n-1) + ... + anb1 ,
......................................................

2009-10-30 19:47:34 補充：
更正為
(*) >= a1bn + a2b(n-1) + ... + anb1 ,