组合构造第2章:从等号成立的条件着手4

组合构造第2章:从等号成立的条件着手4

组合构造第2章:从等号成立的条件着手4

组合构造第2章:从等号成立的条件着手4

【附】为便于有需要者编辑修改,特提供纯文本文档如下:

例9、对于满足条件x 1 +x 2 + … +x n =1的非负实数x 1 ,x 2 ,…,x n ,求

(x j4- x j5)的最大值(第40届IMO中国国家队选拔考试题)。

分析与解:先考虑n=2、3的情形,可发现(x j4- x j5)达到最大时,x 1 ,x 2,…,

x n 中最多有2个不为零。考虑这样的磨光工具:(x,y)→(x+y,0),希望有(x+y)4-(x+y)5+04- 05 >x4- x5+y4-y5。此不等式等价于4x3y+4xy3+6x2y2>5x4y+5xy4+10x3y2+10x2y3,即4x2+4y2+6xy>5x3+5y3+10x2y+10xy2。

上式左边=(x2+y2)+(x2+y2)+6xy≥(x2+y2)+xy+6xy=(x+y)2。

上式右边≤5x3+5y3+15x2y+15xy2=5(x+y)3。

于是,上式成立的一个充分条件是(x+y)2>5(x+y)3,即x+y<。这样,我们得到如下

引理:如果x+y<,则(x+y)4-(x+y)5 >x4- x5+y4-y5。

现在再来解答原题。设x 1 ,x 2 ,…,x n 中不为零的数的个数为k,不妨设x 1 ≥x 2 ≥ …≥x k>0,x k+1= x k+2=…=xn=0,如果k≥3,则令(i=1,2,…,k-2),x' k-1= x k-1+ x k,x' k=0,因为x k-1+ x k≤≤<,由引理,有(x' j4- x' j5)>(x j4- x j5)。

只要非零变量个数不小于3,上述调整就可进行。最多经过n-2次调整,可以将x3、…xn调为0,而S不减。设此时的x1、x2为c、d,则c+d=1,且S=c4(1-c)+d4(1-d)=c4d+cd4=cd(c3+d3)=cd(c+d)(c2-cd+d2)=cd[(c+d)2-3cd]=cd(1-3cd)=。

另一方面,要使S=,则上述一些不等式都成立等号,由此可得,当,,x3=…=xn=0时,S=,故Smax=。

例10、对1,2,…,10的一个排列p=(x1 ,x2 ,…,x10),定义:S(p)= ,其中约定x11=x1。试求:(1)S(p)的最大值与最小值;(2)使S(p)达到最大值的所有排列p的个数;(3)使S(p)达到最小值的所有排列p的个数。

分析与解:(1)由S的轮换对称性,不妨设x1=1,则x10≥2,且对k=1,2,…,9,有|2xk-3xk+1|≥3xk+1-2xk,且|2x10-3x1|≥2x10-3x1。将这些不等式相加得。

另一方面,要使S(p)=57,则上述一些不等式都成立等号,由此可得,当x1=1,xk=12-k(k=2,3,…,10)时,S(p)=57。故Smin=57。

又将S去绝对值符号后,总是有10个正项,10个负项。设有s个负项是2xk型的,t个负项是3xk型的,则S=∑1+∑2+∑3+∑4,其中∑1,∑2分别是2xk型的正,负项之和,∑3,∑4分别是3xk型的正,负项之和,则∑1≤2[10+9+…+(s+1)](注意∑1中有10-s个项),∑2≤-2(1+2+…+s)(注意∑2中有s个项),同样∑3≤3[10+9+…+(t+1)],∑4≤-3(1+2+…+t)。于是。

由于t=10-s,所以

S(p)≤275-2s(s+1)-3(10-s)(11-s)=。

另一方面,要使S(p)=131,则上述一些不等式都成立等号,由此可得,当x1,x2,…,x10分别为8,1,5,10,2,6,9,4,7,3时,S(p)=131。故Smax=131。

(2)若S达到最大值,由(1)中等号成立的条件知,将S去绝对值符号后的正项为2×10,2×9,2×8,2×7,3×10,3×9,3×8,3×7,3×6,3×5,负项为-3×1,-3×2,-3×3,-3×4,-2×1,-2×2,-2×3,-2×4,-2×5,-2×6。

通过穷举可得S去绝对值符号后的正项和负项就是这些项的充分必要条件是:如果将10个数按顺时针方向排成一圈,则1,2,3,4两两不相邻,且分别在1,2,3,4的逆时针方向上和它们紧邻的数恰是7,8,9,10。

这样,为了得到一个使S最大的排列,第一步先将1,2,3,4排在圆周上,使没有两个数相邻,这共有600种方法(先确定1的位置,并不考虑2,3,4的顺序,穷举可得有10种方法,而1有10个可能位置,故共有10×10×3!=600种方法)。第二步将7,8,9,10排在1,2,3,4的逆时针方向上和它们紧邻的空位中,有4!=24种方法。第三步,将5,6排在剩下的空位中,有2!=2种方法。故使S最大的排列有600×24×2=28800个。

(3)设S达到最小值。不妨设x1=1,由(1)中等号成立的条件知,此时x10=2,且2xk≤3xk+1(k=1,2,…,9)……(*)。

由2x9≤3×2得x9=3;由2x8≤3×3得x8=4。由2x7≤3×4得x7=5或6。

①x7=5,此时由2x6≤3×5得x6=6或7。若x6=6,则{x2,x3,x4,x5}={7,8,9,10},且由2x5≤3×6得x5≠10。容易验证只要x5≠10,结论(*)就成立,故此时有4!-3!=18个排列。若x6=7,则{x2,x3,x4,x5}={6,8,9,10},且只要不出现xk=10且xk+1=6的情况,结论(*)都成立,故此时有4!-3×2=18个排列。

②x7=6,此时由2x6≤3×6得x6=5,7,8,9。若x6=5,则由2x5≤3×5得x5= 7。此时{x2,x3,x4}={8,9,10},且结论(*)总成立。此时有3!=6个排列。对x6=8或9,只要不出现xk=8或9且xk+1=5的情况,结论(*)就成立。故此时有2(4!-2×3×2)=24个排列。若x6=7,则只能x2=5,此时结论(*)总成立,故有3!=6个排列。

综上所述,由轮换对称性,使S最小的排列有10(18+18+6+24+6)=720个。

例11、设x1,x2,…,x1990是1,2,…,1990的一个排列,

求F=|…‖x1-x2| -x3| -…-x1990| 的最大值(第24届全苏数学奥林匹克试题)。

分析与解:我们先用两种不同的方法证明F≤1990。

证法1:首先注意到x,y>0时,|x-y|≤max{x,y}。所以

|x1-x2|≤max{x1,x2},||x1-x2|-x3|≤max{max{x1,x2},x3}=max{x1,x2,x3}。

设|||x1-x2|-x3-…-xk|≤max{x1,x2,x3,…,xk},则

|||x1-x2|-x3-…-xk+1|≤max{max{x1,x2,x3,…,xk},xk+1}

=max{x1,x2,x3,…,xk,xk+1}。

所以 F=|||x1-x2|-x3-…-x1990|≤max{x1,x2,x3,…,x1990}=1990。

证法2:对于1,2,…,1990的一个排列x1,x2,…,x1990,

令Fk=|…‖x1-x2| -x3| -…-xk|(2≤k≤1990),则Fk+1=|Fk-xk+1| ,F=F1990。

因为1≤x1≤1990,1≤x2≤1990,0≤|x1- x2|≤1990,即0≤F2≤1990。

设0≤Fk≤1990,而1≤xk+1≤1990,所以 0≤|Fk- xk+1|≤1990,即0≤Fk+1≤1990,于是,对所有正整数n=1,2,…,1990,有0≤Fn≤1990。取n=1990,得F=F1990≤1990。

下面再证明F≠1990。因为|x|≡x≡±x(mod 2),所以

F≡x1-x2-x3-…-x1990≡x1+x2+x3+…+x1990=1+2+…+1990≡1(mod2),

所以 F≠1990,所以F≤1989。

最后构造1,2,…,1990的一个排列:x1,x2,x3,…,x1990,使F=1989。

我们的构造策略是,先从等号成立的条件入手,注意到1990-1=1989,期望构造中有F=|1-1990|=1989。进而从使F=|||x1-x2|-x3-…-x1990|易于计算考虑,期望“代数和”中尽可能多地产生0。于是,希望除1和1990外,其他1988个数相互抵消。再注意到4|1988,从而想到将x1,x2,x3,…,x1988中相继的4个数为一组,分为497组,使每组中4个数xi,xi+1,xi+2,xi+3满足:|||xi- xi+1|- xi+2|- xi+3|=0(*)。

通过尝试4个连续正整数,发现它们适当排列,可满足等式(*)。实际上,我们发现了两种合乎要求的构造。

其一是注意到|||(4k+2)-(4k+4)|-(4k+5)|-(4k+3)|=0,从而令(x4k+1,x4k+2,x4k+3,x4k+4)=(4k+2,4k+4,4k+5,4k+3),其中k=0,1,2,…,496。

其二是注意到对任何正整数n,有|||n+3-(n+1)|-(n+4)|-(n+2)|=0,于是令xi=1990-i(1≤i≤1989),x1990=1990,则F=| x1989- x1990|=|1-1990|=1989。

综上所述,F的最大值为1989。