个人资料
正文

趣味数学 (十三) 强强匹配,积和最大

(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)
评论
目前还没有任何评论
登录后才可评论.