個人資料
正文

趣味數學 (十三) 強強匹配,積和最大

(2013-06-17 06:09:24) 下一個

符號用法:a^n 表示a的n次方,a_n表示a的下標是n, a*b表示a和b的乘積 。符號帶來的不便,請多包涵。

先打一個比方。

如果有n個女孩待嫁,另有n個男孩待娶,怎樣的結合才是最優的呢?我們的祖先說:要講究門當戶對。就是將所有人根據某種條件打個分,把男孩和女孩分別按得分由高到低排一個順序,再將得分最高的男孩和得分最高的女孩配對,得分次高的男孩和得分次高的女孩配對,並以此類推,然後將得分最低的男孩和得分最低的女孩配對,這樣就得到總體的最優婚配。所謂門當戶對,就是強強匹配,或者強強合作。

由這個作引子,我們考慮下麵的數學問題:有兩個n項實數數列A=(a_1,a_2,。。。,a_n)和B=(b_1,b_2,。。。,b_n),通過匹配,我們可以形成另一個n項數列C=(a_1*x_1,a_2*x_2,。。。,a_n*x_n),其中(x_1,x_2,。。。,x_n)是(b_1,b_2,。。。,b_n)的一個排列。總共有n!個不同的排列,從而有n!個不同的n項數列。在這n!個不同的n項數列中,哪一個和最大?也就是,哪一個數列(x_1,x_2,。。。,x_n)能使得和a_1*x_1+a_2*x_2+。。。+a_n*x_n最大?因為匹配而成的數列由乘積而得,我們稱該問題為積和問題。

什麽樣的匹配積和最大呢?

答案是,強強匹配,積和最大。為方便起見,不妨假設a_1,a_2,。。。,a_n按值大小遞減排列。如果y_1,y_2,。。。,y_n也是b_1,b_2,。。。,b_n按值大小遞減排列,那麽(a_1*y_1,a_2*y_2,。。。,a_n*y_n)就是和最大的匹配。

另外,強弱匹配,積和最小。就是說,如果z_1,z_2,。。。,z_n是b_1,b_2,。。。,b_n按值大小遞增排列,那麽(a_1*z_1,a_2*z_2,。。。,a_n*z_n)就是其和最小的匹配。

兩個結論證明都不難,讀者不妨試著證明。我們將結果寫成:強強匹配,積和最大;強弱匹配,積和最小。

當然,也可考慮超過兩個的n項數列匹配問題。比如有三項n項數列A=(a_1,a_2,。。。,a_n),B=(b_1,b_2,。。。,b_n)和
C=(c_1,c_2,。。。,c_n),如何找到數列(y_1,y_2,。。。,y_n)和(z_1,z_2,。。。,z_n)使得它們與A匹配而成的數列
(a_1*y_1*z_1,a_2*y_2*z_2,。。。,a_n*y_n*z_n)積和最大?其中,(y_1,y_2,。。。,y_n)和(z_1,z_2,。。。,z_n)
分別是數列B和C的排列。

因為要包括奇數項的情況,我們假設數列的各項都是非負實數。這時有什麽結論?

我們的結論依然是:強強匹配,積和最大。

自然,對超過兩個的n項數列匹配問題,沒法定義強弱匹配,所以就沒有另一個結論了。

所以,我們的定理是:強強匹配,積和最大。把這個定理弄明白了,就可以證明很多有名的不等式,我們先舉幾例。

1: 算術平均不小於幾何平均:(a_1+a_2+。。。+a_n)/n 不小於 (a_1*a_2*。。。*a_n)^(1/n),等號僅在所有a_1=a_2=。。。=a_n時成立。
2: Cauchy-Schwarz不等式:a_1*b_1+a_2*b_2+。。。+a_n*b_n 不大於 sqrt{(a_1*a_1+a_2*a_2+。。。+a_n*a_n)(b_1*b_1+b_2*b_2+。。。+b_n*b_n)}。

有興趣的朋友不妨試著證明一下。

根據這個定理,我們證明下麵的結論。如未說明,a,b,c,d均為非負實數。

1:如a正實數,則a+(1/a)>=2。
證: 考慮二元數列(1,a)和(1,1/a)。注意它們的強弱匹配是(1*1,a*(1/a))其和為1*1+a*(1/a)=2,另一個匹配是(a*1,1*(1/a))其和為a+(1/a)。

2: a^2 + b^2 + c^2 >= a*b+b*c+c*a。
證: 考慮二元數列(a,b,c)和(a,b,c)。它們的強強匹配是(a*a,b*b,c*c),其和為a^2 + b^2 + c^2;另一個匹配為(a*b,b*c,c*a),其和為a*b+b*c+c*a。

3:a^3+b^3+c^3 >= 3a*b*c。
證: 考慮三元數列(a,b,c),(a,b,c)和(a,b,c)。它們的強強匹配是(a*a*a,b*b*b,c*c*c)其和為a^3 + b^3+ c^3,(a*b*c,b*c*a,c*a*b)是另一個匹配,其和為:3a*b*c。

4:a/b+b/c+c/d+d/a>=4。
證: 考慮兩個四元數列(a,b,c,d)和(1/a,1/b,1/c,1/d)。它們的強弱匹配是(a*(1/a),b*(1/b),c*(1/c), d*(1/d))其和為4,(a/b,b/c,c/d,d/a)是另一個匹配,其和為:a/b+b/c+c/d+d/a。

 5: (a^2)/b + (b^2)/c + (c^2)/d + (d^2)/a >= a + b + c + d。
證:考慮數列(a^2,b^2,c^2,d^2)和(1/a,1/b,1/c,1/d),它們的強弱匹配是((a^2)/a,(b^2)/b,(c^2)/c, (d^2)/d))=(a,b,c,d); ((a^2)/b,(b^2)/c,(c^2)/d,(d^2)/a)是另一個匹配。

還可以舉出很多例子,用強強匹配定理或強弱匹配定理就可給出簡單的證明。

[ 打印 ]
閱讀 ()評論 (0)
評論
目前還沒有任何評論
登錄後才可評論.