离散量的最值问题

离散量的最值问题所谓离散量最值问题，即指自变量是整数，集合、子集、点、线，图等离散量，要求它们在满足某些约束条时，求目标函数的最大值或最小值问题。离散最值问题涉及的面非常广泛，也是近年来国内外数学竞赛中经常出现的热点问题。由于整数等自变量的离散性，通常关于求连续变量的最值问题的方法不再适用。所以解决这类非常规的离散最值问题，对于参赛的同学的聪明才智具有更大的挑战性。下面介绍解离散最值问题的几种主要方法。一、不等式法不等式法解离散最值问题包括两个方面：论证估值与构造实例。论证估值即是根据问题中的离散变量具有的性质建立不等式，然后通过对不等式的放缩来论证或者估计离散变量的最佳的上界或下界；构造实例即是找到一个实例以说明离散变量在约束条件下，目标函数可以达到这个最佳的上界或下界，于是这个上界或下界即是所求的最大值或是小值。123nN，求皿(TWn-的最大值12000年全国高中数学联赛试题）。解nN123nN，求皿(TWn-的最大值12000年全国高中数学联赛试题）。解nNf(n)，有Sn (n32)Sn1nn(n1)21n322(n1)n2)n234n6434164由均值不等式有6434n2,'n646434n2,'n64 34n50故细Fn15064注意到上面价值不等式中等号成立的充要条件是n ，即64注意到上面价值不等式中等号成立的充要条件是n ，即nn8，而f(8)150°综上，f（n）的最大值为秒。50例2已知例2已知n个（n2）正整数X],X一,。且满足x1xn。若有n求xn的最大值。n解首先估计X的上界。注意到Xn1 2,否则,，若X11 n11，则有X] x2Xn1 1。于是n1矛盾！XX1解首先估计X的上界。注意到Xn1 2,否则,，若X11 n11，则有X] x2Xn1 1。于是n1矛盾！XX1-4 2-XX12x nxnXX12X(n

n1)xxnnxx1x2n2，则有xx2x3nxx1x3nx2nxx112(n1)12(n 1)n22(n2n1)2n2矛盾！故xn。nT面构造一个Xnn的实例。X2n1n，则有xx122n。综上，所求X的最大值为n。n39,1in）。全部学生例3某市有n所中学，第i所中学派出39,1in）。全部学生n总数为c1990，看台上每一横排有199个座位。要求同一学校的学生必须坐在同一横排。向体育馆ii1最少要安排多少个横排才能保证全部学生都能坐下，（1990年全国高中数学联赛试题）。分析首先利用条件初步估计最小横排数的上界13，即“随便坐，13排足够”；其次利用极端性原理考虑空位最小的原则，精确估计最小横排数的最佳上界12，即“巧安排，，12排够用”；最后构造反例说明：11排一定坐不下，所以所求最小横排数为12。解已知每个C39,故每一横排至少可坐161人，否则不足161人将至少留下39个空位，从而尚可i安排一具学校的学生坐下。于是只要有13排，至少可坐161132093人，当然能坐下全部1990人，这说明，随便坐，13排正够。下面我们说明巧安排，12排就够用了。为了使横排数最少，应使各排的空位数尽可能少，所以应该依据空位最小的原则来进行安排。因为口所学校的学生数叩c2,c是有限个数，故它们的不超过199的有限和只有有限个。记12nC1c 乞为其中最接近（＜1990）199的有限和则可将这k个学校的学生安排在第1排就座。无i1i2 ik疑，这样安排最充分有效地利用了第一排的座位。然后再在余下的c中选取最接近199的限和，并将其中这些学校的学生安排在第2排。依此类推，一1直到第10排，记第i排的空位数为X.1i10），显然有

因为12排共有1991239812xxx因为12排共有1991239812xxx12102388个座位，坐满1990个人，尚余23881990398个空位，而33。故下面分两种情况讨论％。若xi033。则余下听未入座的每个学校的学生数Cj34。如果余下的学校数4,注意到394156199，将他们全部安排在第11排即可即此的仅需安排11排便可使全部1990人入座。如果余下的学校数5,则完全可以任取5个学校的学生坐在第11排,而且在少坐345170人,从而x11 29x10,这与％的最小值矛盾。即这种情况是不会出现的。若x10 32，则前10排空位总数10x10x10x10x10320。于是前10排所坐学生总数不小于199103201670，从而未入座的学生数不大于19901670320。由于每一横排至少坐161人，故再安排2排就可以使入座的学生坐下。即此仅需安排12排即可使全部1990人入座。最后，我们构造反例说明仅安排11排是不行的。设n80,其中有79个学校每校25人，有1个学校15人，共计257915 1990人。因为除第1排可以坐25715190人之外，其余10排每排至多坐257175人，所以11排至多坐190175101940人。这说明11排是不够全部学生入座的。综上，所求最小横排数为12。例4平面上有n个点，其中任意三点不共线，每两点间用线段相连，用红蓝两种颜色将每条线段染色。若对任何染色法，一定存在12个同色三角形，求n的最小值。解为估计n的下号，我们引入异色角的概念。若一个角的两边不同角，则称这个角为异色三角形恰有两个异色角。n个点可构成C3个三角形，由条件可知其中至少有12个同色三角形，于是至多有C3 12个异角nn三角形，从而至多有2(c3 12)个异色角。这说明对于任何染色法，异色角总数若不超过2(c3 12)，nn则必存在同色三角形。另一方面，设n个点为A.(i12n)，从任一点A.出发，可引n1条线段，设其中有r条红线，i in1n1r条蓝线。于是以A.为顶点的异色角数为r(ni i i1r)条，从而异色角总数nri(n1r)。由i i ii1均值不等式r(n1r(n1r)

ii(罟)1)1)r(n1r)iii1由上面分析可知，若n的取值满足不等式n(」)2 2@ 12)2n则必存在12个同色三角形。解此不等式得n9。T面举反例说明n8时，不存在12个同色三角形。当n8时，过每点的7条线均染三红四蓝，则48个，从而同色三角形只有异色角总数为8 (34) 96个，于是异色三角形总数为£96c3485648848个，从而同色三角形只有8综上，所求n的最小值为9。例58位歌手参加艺术节，准备为他们安排m次演出，每次由其中4位登台表演，要求8位歌手中

任意两位同时演出的次数都一样多。请设计一种方案，使得演出的次数山最少(1996年中国冬令营试题)。分析首先通过对于c2对歌手总共同时演出的次数进行两个方面的估算(也称“算两次”得到m的8下界；然后构造一个实例，即设计一种演出方案，使m可以达到这个下界，于是这个下界即是m的最小值。解设任意两位歌手都同时演出r次。一方面，共有c2对歌手，每对歌手同时演出r次，他们总共同8时演出rc2次。8另一方面，每次演出有4人登台，从而每次演出有c2对歌手同时演出，由于共演山次，所以他们总4共同时演出。mc2次。4综合两方面有rc2 mc2，即14r3m。由此知3|r，故r3，于是m14。84下面设计一个演出方案，说明m 14(r3)是可行的。用1，2,…，8代表8位歌手，用(a,b,c,d)表不一次演出:(1,2,3,4),(5,6,7,8),(1,4,5,8),(2,3,6,7)(1,2,5,6),(3,4,7,8),(1,3,5,7),(2,4,6,8),(3,4,5,6),(2,3,5,8),(1,4,6,7),(2,4,5,7).在上面14个括号内，由于每对数字恰出现在3个括号内，即任意两位歌手同台演出恰为3次，所以m的最小值为14。例6试求出具有如下性质的最小的正整数n:n可以表示为2002个各位数字之和相等的正整数之

和，又可以表示为2003个各位数字之和相等的正整数之和。(2002年第28届俄罗斯数学奥林匹克试题)naaabbb2002 1 2 2003解假设对正整数nnaaabbb2002 1 2 2003由于aa,a 的各位数字之和相同，所以它们被9除的余数相同，记该余数为r(0r8)。122002同理，bb ,b 被9除的余数相同，记为s(0s8)o1 2 2003于是，9|n2002r且9|n2003s，从而9|(n2002r)-(n2003s)=2003(rs)4005r。注意到9|4005，且(9,2003) 1，故9|(rs)。若rs0,则rs0,由于b,b,,b均被9整除，故此为n92003；1 2 2003若rs0，则rs9，于是r与s中至少有一个不小于5。故此为n52003或n52002。下面考虑5200210010的两种符合要求的分析：一方面，1001055 5(2002个5)另一方面,10010420022002144 42002(2002个4与1个2002)综上，口的最小值为10010。二、调整法许多离散最值问题可以看作是涉及到有限多个元素的系统。系统的状态是有限多，因而值的状态。X692。因为TOC\o"1-5"\h\z例7已知廿2 X69 N，且X1 X2 X69 112，求X12 X2X692。因为(x1)2(x 1)2x2x222(xx)x2x21 69 1 69 69 1 1 69这说明将最小数^减少1，而将最大数X增加1，和不变，但平方和增大。为此，我们每次调整都将’减1 69 1少1，将减少的1加到X上，直到X1为止，这样调整的结果便得69个正整数的和为112不变，而平69 1方和在调整前增大了。再将x2解冻，对x2调整，幻然是每次将x2减少1，将x加上，直到X” 1为止。2 2 69 2如此对x,x,,x—步一步地调整下去，直到将(x,x,,x,x)调整到1,1,,1,44)。4 66 1 2 68 69此时，因为11 144 6844112，并且每调整—次，平方和就增大—次，所以x2x2x2的最大值为1 2 6912 12 12 442 681936 2004例8 155只鸟停在一圆周C上，记为P1i155)，如果pp10,称P与p.是相互可见的,i ij ij求互相可见的鸟对的最小数(假定一个位置上可以同时有n个鸟)。分析欲求互相可见的鸟对的最小值。首先用调整法证明鸟在圆周C的落脚点至多只有35处时，即

一对鸟只有在同一处才互相可见时才是最佳状态；其次再用调整法证明任何两处的鸟数至多差1时才是最佳状态；最后计算最佳状态时的可见对的最小值。解设鸟p.停在圆周C的A处，鸟p.停在圆周C的B处，(AB)P.与P.可见。设k为从B可ijij以看到而从A处看不到的鸟的只数，l为从A处可以看到而从B处看不到的鸟的只数，且设k1。如果将B处的所有鸟调整到A处，则对B每只鸟都减少了k个可见对而增加了1个可见对，所以互相可见的对数减少kl时。经过如上调整，重复若干次调整，直到每两只鸟只有在同一位置时才互相可见,这时有鸟的位置最多有35处，于是问题化为在条件xxx1551235之下，求c2x35的最小值。其中每个x. 1i35)为非负整数，当x.i下面再对每处鸟的只数进行调整，不妨设X]min1.352时，约定c2XimaXXi，X20c2x35的最小值。其中每个x. 1i35)为非负整数，当x.i下面再对每处鸟的只数进行调整，不妨设X]min1.352时，约定c2XimaXXi，X20。xi。1i35若x22，则令x2'35X11，这样调整后i1x的值不变，i而由于c2

x12c2c1x'x'12x(x1)2x(x1)(x1)x—22112(x1)(x0,2)x211所35以Ci1要减少。继续调整，直到x21，然后再选择Xi(1ii35)中的最大数与最小数如此调整，注意到4最后，155 5,所以经过有限次调整，计算可见对时最小值。设有m处停4只鸟，有n处停5只鸟，于是有可以使所有X.为4或5。此时，可见对取最小值。imn35,4m5n155.解得m20，n15，所有可见对的最小值为20c215c2270。45即圆周上取35个位置(相邻两点的劣弧大于10)，其中20个位置各停4只鸟，15个位置各停5只鸟可见对可以达到最小值270对。三、差分法求离散变量函数f(n)(nZ)的最值问题时常用到差分法，即通过考察正数的一阶差分f(n)f(n1)f(n)的符号，以确定f(n)的单调区间，从而求其最值。

例9试求函数f(n)1n例9试求函数f(n)1n32n2(nZ)0时，0时，f(n)2综上可知，2综上可知，f(n)的最大值为f6)19f(n)f(n1)f(n)1(n1)1n(n23n31)、易知，当032(n1)232n2(332nn2)(32n2n23n310，于是f(n)0，从而f(n1)f(n)，即f(5)f(4)f(1)f(0) 0.而当n5时，有n23n310，于是f(0)0，从而f(n)f(n1)，即0,故下面只考虑n取非负整数的情况。先计解当n算一阶差分f(5)f(6)f(7)n4时，有例10试求函数f(n)1966nf(n)1966n(nN)n!的最大值。解当1n18时，因为19(n1)!19n119n!19nn!，66n1(n1)!66n166n66nn!n!所以一阶差分f(n)f(n1)f(n)0,即f(19)f(18)f(1)当n19时，因为(n1)!19(n1)!19n119n!19nn!，66n1(n1)!66n166n66nn!n!所以一阶差分f(n)f(n1)f(n)0,即f(19)f(18)f(1)当n19时，因为(n1)!f(n)19n166n1(n1)(19n66n)66n(66n1)19n(n119)0,19n640,n65所以有f(n)f(n1)f(n)0,0,n64即f(65)f(64)f(19),且f(65)f(66)f(67)综上可知，f(n)综上可知，f(n)的最大值为f(65)1965 666565!__练习题设M 1,2, ,1995,A是M的子集且满足条件：当xA时，15xA。试求A中元素个数的最大值.10人到书店买书，已知(1)每人都买了3种书；(2)任何两人所买的书中，都至少有一种相同。问购买人数最多的一种书最少有几个人购买？m个互不相同的正偶数和n个互不相同的正奇数的总和为1987，试求3m4n的最大值。12个朋友每周聚餐一次，每周分成三组，每组4人，不同组坐不同的桌子，若要求这些朋友中任意两个人至少有一次同坐一张桌子，问至少需要多少周？已知a 1,a3,a(n3)a(n2)a.若当mn时，a的值都能被9整除，求n1 2 n2 n1 n m的最小值。已知若干个正整数之和为1976，求其积的最大值。设nN,1n100，求f(n)n(100n)(100n1)的最大值。1000n8•设nN,求f(n)—的最大值。n!练习题答案1.令A1,2, ,8，A9,10, ,133，2A3 134,135, ,1995，因为xA?，必有15xA^所以x与15x这两个数中至少有一个不属于A。从而应有TOC\o"1-5"\h\z|A||M||A|1995125 1870.2又因为xA，恒有15xA(i1,2,3)。另一方面xA,15xA。所以可构造AAA,i i 1 3 1 3则A满足条件，且|A||A1||A3|81862 1870.综上，1A的最大值为1870。2•设购买人数最多的一种书有x个人购买。设A是10人之一，已知A买了3种书，且其余9人中每人所买的书中都至少有一种与A相同，由抽屉原则知9人中至少有3人，加上A共4人买了同一种书，故x4。若x4,则A的3种书均为4人购买。同理，其它9人的每种书也均有4人购买。所以10人所买书的总数应是4的倍数，即4130,矛盾，所以x5。

下面构造例子说明X5可行。设a为互不相同的书，10人买书情况如下ia,a,a,a,a,a,a,a,a,123126234(a,a,a),(a,a,a),a,a,a,1 4 16145245(a,a,a),135(a,a,a),256(a,a,a),356a,a,a.346上述购书情况符合要求，故购买人数最多的一种书最少有5人购买3•设a,a,12,a是互不相同的正偶数，b,b..,bn2是互不相同的正奇数，使得b1987nmaa1212abbm1此时，aaa242mm(m1),12mbbb13(2n1)n2.12n于是有m2mn21987.因而有121m n2198724由柯西不等式有14n<32 42i 1213m—'m n25,1987-2■ 724注意到3m4n的整数，所以3m4n221.另一方面，当m 21,n35时°m2mn219811987，且3m4n221.所以3m4n的最大值为221。4•因为12人共有c266对，而每张桌有c26对，第一周有3618对同桌。第一周后的每12 4一周，同桌4人来自第一周的3桌，故其中至少有两人第一周已经同桌，即每桌产生的新的同桌对至少有6-1=5对，共计15对。于是4周至多有同桌对181515156366.所以n4不行。即n