趣味数学 (十三) 强强匹配

朝霞满天 · 2013-06-17 17:53:03Z

趣味数学 (十三) 强强匹配简介

来源: 朝霞满天于 2013-06-17 17:53:03 [档案] [博客] [旧帖] [给我悄悄话] 本文已被阅读：次 (4844 bytes)

符号用法：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*b_1+a_2*b_2+。。。+a_n*b_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)是另一个匹配。

还可以举出很多例子，用强强匹配定理或强弱匹配定理就可给出简单的证明。