高中数学竞赛专题讲座---离散极值.doc

离 散 极 值一. 知识与方法 所谓离散极值，就是指以整数、集合、点、线、圆等离散对象为背景，求它们满足某些约束条件的极大值或极小值。这类问题的解法与一般函数（连续变量）极值的解法有很大的差异。对于这类非常规的极值问题，要针对具体问题，认真分析，细心观察，选用灵活的策略与方法，通常可以从论证与构造两方面予以考虑。先论证或求得该变量的上界或下界，然后构造一个实例说明此上界或下界可以达到，这样便求得了该离散量的极大值或极小值。在论证或求解离散量的上界或下界时，通常要对离散量做出估计，在估计的过程中，构造法、分类讨论法、数学归纳法、反证法、极端原理、抽屉原理等起着重要的作用。二. 范例选讲例1. m个互不相同的正偶数和n个互不相同的正奇数的总和为1987，对于所有这样的m与n，问3m+4n的最大值是多少？请证明你的结论。（1987年第二届全国数学冬令营试题）思路分析：先根据题设条件求得3m+4n的一个上界，然后举例说明此上界可以达到，从而得到3m+4n的最大值。解：设a1,a2,am是互不相同的正偶数，b1,b2,bn是互不相同的正奇数，使得a1+a2+am+b1+b2+bn=1987 ，这时分别有：a1+a2+am2+4+2m=m(m+1) ，b1+b2+bn1+3+(2n-1)=n2，由,得m²+m+n21987,因而有（m+）2+n2 ，由及柯西不等式，得3（m+）+4n,由于3m+4n为整数，所以3m+4n ，另一方面，当m=27,n=35时，m2+m+n2=1981<1987,且3m+4n=221。故3m+4n的最大值为221。评注：在论证过程中用到了柯西不等式与一般二元一次不定方程的求解方法。例2. 设空间中有2n(n2)个点，其中任何四点都不共面。将它们之间任意连接N条线段，这些线段都至少构成一个三角形，求N的最小值。思路分析：通过构造实例，说明Nn2+1，进而证明当N=n2+1时，若在2n点间连有N条线段，则这些线段至少构成一个三角形。其证明过程可用数学归纳法或反证法或极端原理，在证明过程中要精打细算。 解法一：将2n个已知点均分为S和T两组：S=A1，A2，An，T=B1，B2，Bn。现将每对点Ai和Bj之间都连结一条线段AiBj，而同组的任何两点之间均不连线，则共有n2条线段。这时，2n个已知点中的任何三点中至少有两点属于同一组，二者之间没有连线。因而这n2条线段不能构成任何三角形。这意味着N的最小值必大于n2。下面我们用数学归纳法来证明：若在2n个已知点间连有n2+1条线段，则这些线段至少构成一个三角形。当n=2时，n2+1=5，即四点间有五条线段。显然，这五条线段恰构成两个三角形。设当n=k（k2）时命题成立，当n=k+1时，任取一条线段AB。若从A，B两点向其余2K点引出的线段条数之和不小于2k+1，则必定存在一点C，它与A，B两点间都有连线，从而ABC即为所求。若从A，B两点引出的线段条数之和不超过2K，则当把A，B两点除去后，其余的2K点之间至少还有K2+1条线段。于是由归纳假设知它们至少构成一个三角形，这就完成了归纳证明。综上可知，所求N的最小值为n2+1。 解法二：构造例子同解法一，可知所求的N的最小值不小于n2+1。由于2n个点间连有n2+1条线段，平均每点引出n条线段还多，故可猜想必定有一条线段的两个端点引出的线段数之和不小于2n+1，让我们用反证法来证明这一点。设从A1，A2，A2n引出的线段条数分别为a1，a2，a2n且对于任一线段AiAj都有ai+aj2n。于是，所有线段的两个端点所引出的线段条数之和的总数不超过2n（n2+1）。但在此计数中，Ai点恰被计算了ai次，故有2n（n2+1） ，另一方面，显然有=2（n2+1）由柯西不等式有（）22n（），×4（n2+1）22n（n2+1） ，与矛盾。从而证明了必有一条线段，从它的两个端点引出的线段数之和不小于2n+1。不妨设A1A2是一条这样的线段，从而又有Ak（k3），使线段 A1Ak，A2Ak 都存在，于是A1A2Ak即为所求。 解法三：构造例子同解法一，可知所求的N的最小值不小于n2+1。下面我们用极端原理来证明，当N= n2+1时，这些线段至少构成一个三角形。从而所求的N的最小值即为n2+1。设2n个已知点间连有n2+1条线段，且这些线段不构成任何三角形，设A是2n点中引出线段条数最多的一个点，共引出k条线段：ABj，j=1，2，k。于是B1，Bk之中任何两点间都没有连线，否则必构成三角形。因而，从任一Bj引出的线段条数不超过2n-k。除了A，B1，Bk之外还有2n-k-1点，其中任何一点引出的线段条数当然不超过k。于是得到n2+1k+k(2n-k)+(2n-k-1)k=k(2n-k)n2,矛盾，这就完成了全部证明。评注：本题用了三种方法求解，都是先通过例子确定出N的一个下界，然后用不同的方法证明这个下界是可以达到的，进而求出N的最小值。解法一用到数学归纳法，解法二运用了反证法与柯西不等式，解法三则是运用了极端原理。例3. 集合A的元素都是整数，其中最小的是1，最大的是100。除1以外，每一个元素都等于集合A的两个数（可以相同）的和。求集合A的元素个数的最小值。思路分析：先构造一个合乎条件的集合A，说明A的元素个数的最小值不可能比9大，再进一步说明A的元素个数的最小值就是9。 解：构造一个元素个数尽可能少的集合使它满足条件，如：1，2，3，5，10，20，25，50，100，则集合A的元素个数的最小值不大于9。若1，2，x1，x2，x3，x4，x5，100也满足条件，则x14，x28，x316，x432，x564。但x4+x5=96100，x5=50，x3+x4=4850，x4=25，x2+x3=2425，x3=，与x3是整数矛盾。故A的元素个数的最小值是9。评注：先构造的例子说明集合A的元素个数的最小值小于或等于9，后论证A的元素个数不可能小于9，这里运用了反证法。例4. 平面上给定n个点A1，A2，An（n3），任意三点不共线。由其中K个点对确定K条直线（即过K个点对中的每一点对作一条直线），使这K条直线不相交成三个顶点都是给定点的三角形，求K的最大值。思路分析：先对n个点中的点对A1，A2进行分析，然后再对其余n-2个点中的点对A3，A4分析，逐步类推，对K的上界进行估计，然后通过实例说明K的上界可以达到，进而求得K的最大值。 解：设过点对A1，A2的直线为L，则 A1，A2不能同时与其余n-2个点中的任意一点连结，即过A1或A2的直线至多有n-1条（包括L）。同理，对A3，A4，An这n-2个点而言，过A3或A4的直线至多有n-3条，。所以K（n-1）+（n-3）+=另一方面，我们可以把n个点分成两组：n为偶数时，每组各个点；n为奇数时，一组个点，一组个点。把第一组的每点与第二组的每点连结成或条直线，这些直线不相交成三个顶点都是给定点的三角形。所以，当n为偶数时，k的最大值是,当n为奇数时，k的最大值是。评注：本题在对K进行估计时，要对n分奇数，偶数进行讨论。例5. 空间中有1989个点，其中任何三点都不共线。把它们分成点数各不相同的30组，在任何三个不同的组中各取一点为顶点作三角形。试问要使这种三角形的总数最大，各组的点数应为多少？（1989年全国中学生数学冬令营试题）思路分析：先把1989个以知点分成个数分别为n1，n2，n30的30组，其顶点在三个不同组的三角形总数可表示为S=，然后通过逐步调整法求S的最大值。解：设1989个已知点分成30组，各组的点数分别为n1，n2，n30.因此，顶点在不同组的三角形的总数为S=于是，本题即是问在且n1，n2，n30互不相同的条件下，S在何时取得最大值。由于把1989个点分成30组只有有限种不同的分法，故必有一种分法使S达到最大值。设n1<n2<<n30为使S达到最大值的各组的点数。（1）对于i=1,2,29，均有ni+1-ni2。若不然，设有i0使ni0+1-ni03，不妨设i0=1这时我们改写S=n1n2+（n1+n2）+。令n=n1+1，n=n2-1，则n< n<n3，n+ n= n1+ n2，n n= n1 n2 + n2- n1-1> n1 n2。所以当用n ，n代替 n1，n2时，将使S变大，矛盾。（2）使ni+1-ni=2的i值至多一个。若有1io<jo29，使nIo+1-nIo=2，njo+1- njo=2，则当用n=nio+1，n=njo+1-1代替nio，njo+1时，将使S变大，这不可能。（3）若30组的点数从小到大每相邻两组都差1，设30组的点数依次为K-14，K-13，K，K+1，K+15，则有（K-14）+（K-13）+K+（K+1）+（K+15）=30K+15，这时点的总数为5的倍数，不可能是1989。故知n1<n2<<n30中，相邻两数之差恰有一个为2而其余的全为1。（4）设nj=其中1io29。于是有+=1989，30m-io=1524，由此解得m=51，io=6。所以当S取得最大值时，30组点数依次为51，52，56，58，59，81。评注：本题运用逐步调整的方法，得到了使S取最大值的必要条件和充分条件，其间运用了反证法。例6. 某市有n所中学，第i所中学派出Ci名学生到体育馆观看球赛（1Ci39，i=1，2，n），全部学生总数为=1990。看台上每一横排有199个座位。要求同一学校的学生必须坐在同一横排。问体育馆最少要安排多少横排才能保证全部学生都能坐下？（1990年全国高中数学联赛二试）思路分析：利用1Ci39，对每排至少可坐的学生人数或每排至多可留出的空位数进行分析，确定出至少需要的横排数。 解：由于1Ci39，故每一横排至少可坐161人，于是只要有13排，至少可坐161×13=2093人，当然能坐下全部学生1990人。下面我们来看12排座位能否安排下全部学生。注意，这时共有199×12=2388个座位，坐了1990人后，还有398个座位。因此，如果每排的空位数都不超过33个，便可安排下全部学生。将所有学校学生从多到少重新编号，于是有C1C2C3Cn。这样存在非负整数m，使Cm34而Cm+133。（若m=0，则意味着所有Ci都不超过33）。设m=5p+r（0r5）。将前5p个学校的学生安排在前p排就坐，每排5个学校，每排至少坐170人，空位至多29个。接下去按次序使其余学校的学生就坐，每排都是坐到不能全部坐下下一学校的学生为止，则每排的空位都不会超过32个，直到第11排为止。这11排空位不超过32×11=352个，所以至少已坐了1837人，全部中学生中至多还有1990-1837=153人没坐下，当然可将他们安排在第12排就坐。可见，只要有12排座位，即可使全部学生按要求就坐。最后，让我们来看，只有11排座位情形如何？这时，只有199个空位，要想安排下全部学生，每排空位平均不能达到19个。现设n=80，前79所学校各有25人，最后一个学校有15人，则25×79+15=1990。除了一排可以安排25×715=190人就坐之外，其余10排至多安排175人，故11排至多安排190175×10=1940人就坐。这个例子说明只有11排座位是不够的。因此，为了安排下1990名学生，最少需要12排座位。评注：为了求得横排数的最小值，先进行估计，说明12个横排可以达到要求，在论证过程中，以数字33作为分界线，精确计算，达到了目的。然后通过构造实例说明11个安排不够。例7. 设S=1，2，10，A1，A2，Ak是S的子集，满足条件：（1）Ai=5（i=1，2，k）；（2）AiAj2（1i<jk）。求K的最大值。（1994年国家集训队试题）思路分析：应当根据子集满足的条件推导出一个K的上界。作如下试探：令A1=1，2，3，4，5,各子集间至多有2个公共元，令A2=1，2，6，7，8，此时，若1，2 A3，则必有A1A33或 A2A33 矛盾。由此得到第一个猜想：A1 ，A2， Ak中至多有两个集合包含同一个2元子集。令A3=1，3，6，9，10，此时，若1A4，则此时A1 ，A2，A3中除1外均至多还有一个元素同时属于A4，A44，矛盾。由此得到第二个猜想：S中每一个元素至多属于A1，A2，Ak中的3个集合。此时可求得K的一个上界。 解：（1）对S的任意一个2元子集a，bS，A1 ，A2，Ak中至多有两个集合包含a，b。否则，设有A1a，b，A2a，b，A3a，b，则由于AiAj2（1i<jk），所以Ai-a，b两两不交（i=1，2，3），上述Ai-a，b表示差集：A-B=xxA且xB。但Ai-a，b=3（i=1，2，3），于是S3×32=11，矛盾。（2）对S的任意一个元素a，A1，A2，Ak至多有三个集合包含a。设已有A1a，A2a，A3a，若AiAj=1（1i<j3），则A1 A2 A3=3×41=13，矛盾。设ba，且a，bA1A2，则A1 A2=8，根据（1），bA3且A3A12，A3A22，所以A3中至多还有2个元素不属于A1 A2，即 A3。同理，若还有A4a，那么 A4，从而A3A43，矛盾。故对任意aS，a至多属于A1 ，A2， Ak中3个子集，所以S中每个元素至多在A1 +A2+ +Ak中作了3重计数，故A1 +A2+ +Ak3S=30，所以K6。按照上述思路，可构造出符合条件的6个子集：1，2，3，4，5，1，2，6，7，8，1，3，6，9，10，2，4，7，9，10，3，5，7，8，10，4，5，6，8，9故K的最大值为6评注：从探求必要条件入手，再验证其充分性，这种从必要到充分的思想方法也是数学竞赛中一种常用的思想方法。例8. 设S=1,2,3,280，求最小的正整数n，使得S的每个有n个元素的子集都含有5个两两互素的数。思路分析：先通过构造S的子集，得到n的下界；然后再通过构造S的另一类子集，又说明n的上述下界可以达到，从而确定出n的最小值。解：设A1=S中被2整除的数，A2=S中被3整除的数，A3=S中被5整除的数，A4=S中被7整除的数，并记A=A1A2A3A4，则利用容斥原理计算得|A|=216，由于在A中任取5个数必有两个数在同一个Ai中(i=1,2,3,4)，且不互素，故n217.另一方面，设B1=1和S中的一切素数，B2=22,32,52,72,112,132，B3=2×131,3×89,5×53,7×37,11×23,13×19，B4=2×127,3×83,5×47,7×31,11×19,13×17，B5=2×113,3×79,5×43,7×29,11×17，B6=2×109,3×73,5×41,7×23,11×13，记B=B1B2B6,则|B|=88，于是S-B含有192个元素。在S中任取217个数，由于217-192=25，故至少有25个元素在B中，且25=4×6+1，故这25个元素中必有5个数属于同一Bi,显然他们两两互素。故n的最小值为217。评注：根据问题的特点，构造恰当的子集族是完成本题解答的关键。例9. 如图，在7×8的长方形棋盘的每个小方格的中心点各放一个棋子。如果两个棋子所在的小方格共边或共顶点，那么称这两个棋子相连。现从这56个棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线（横、竖、斜方向）上依次相连。问最少取出多少个棋子才可能满足要求？并说明理由。（2007年高中数学联赛加试试题） 解：最少要取出11个棋子，才可能满足要求。其原因如下：如果一个方格在第i行第j列，则记这个方格为(i，j)。第一步证明若任取10个棋子，则余下的棋子必有一个五子连珠，即五个棋子在一条直线（横、竖、斜方向）上依次相连。用反证法。假设可取出10个棋子，使余下的棋子没有一个五子连珠。如图1，在每一行的前五格中必须各取出一个棋子，后三列的前五格中也必须各取出一个棋子。这样，10个被取出的棋子不会分布在右下角的阴影部分。同理，由对称性，也不会分布在其他角上的阴影部分。第1、2行必在每行取出一个，且只能分布在(1，4)、(1，5)、(2，4)、(2，5)这些方格。同理(6，4)、(6，5)、(7，4)、(7，5)这些方格上至少要取出2个棋子。在第1、2、3列，每列至少要取出一个棋子，分布在(3，1)、(3，2)、(3，3)、(4，1)、(4，2)、(4，3)、(5，1)、(5，2)、(5，3)所在区域，同理(3，6)、(3，7)、(3，8)、(4，6)、(4，7)、(4，8)、(5，6)、(5，7)、(5，8)所在区域内至少取出3个棋子。这样，在这些区域内至少已取出了10个棋子。因此，在中心阴影区域内不能取出棋子。由于、这4个棋子至多被取出2个，从而，从斜的方向看必有五子连珠了。矛盾。图1图2第二步构造一种取法，共取走11个棋子，余下的棋子没有五子连珠。如图2，只要取出有标号位置的棋子，则余下的棋子不可能五子连珠。综上所述，最少要取出11个棋子，才可能使得余下的棋子没有五子连珠。三. 训练题1. 对有限集A，存在函数f:A,具有下述性质：若i,j,且|i-j|是素数，则f(i)f(j)，问集合A中至少有几个元素？2. 10人到书店买书，已知（1）每人都买了三种书；（2）任何两人所买的书中，都至少有一种相同。问购买的人数最多的一种书最少有几个人购买？3. 在一个有限的实数数列中，任何七个连续项之和都是负数，而任何十一个连续项之和都是正数，试问这样的数列最多能有多少项？4. 给定平面上的点集P=P1,P2,P1994,P中任三点不共线，将P中点任意分成83组，使每组至少有3个点，每点恰好属于一组。将每组中任二点均连成一线段，不在一组的两点不连线段。这样得到了一个图G。显然，不同连接线段的方式，得到不同的图。图G中所含以P中点为顶点的三角形的个数记为m(G)。 （1）求m(G)的最小值m0; （2）设G*是使m(G*)=m0的一个图，若将G*中的线段用4种颜色染色，每条线段恰好染一种颜色。则存在一种染色法，使G*中线段染色后，不含同色边三角形。5. 在7×7个小方格的正方形里，划出K个小方格的中心，使其中任何四个点都不是其边与正方形的边平行的矩形的顶点，这种K的最大可能值是多少？6. 在100×25的长方形表格中每一格填入一个非负实数，第i行第j列中填入的数为xi,j(i=1,2,100;j=1,2,25)，如表1。然后将表1每列中的数按由大到小的次序从上到下重新排列为x1,jx2,jx100,j(j=1,2,X1,1X1,2X1,25X2,1X2,2X2,25X100,1X100,2X100,25X1,1X1,2X1,25X2,1X2,2X2,25X100,1X100,2X100,2525),如表2。求最小自然数K，使得只要表1中填入的数满足，则当iK时，在表2中就能保证成立。 表1 表2四. 训练题提示或解答1. 解：因为1,3,6,8这四个数字中任何两个数字的差的绝对值均为素数，由题意知f(1),f(3),f(6),f(8)是A中四个两两不等的元素。从而|A|4.另一方面，若令A=0,1,2,3,f:A的对应关系为：若x,x=4k+r,则f(x)=r,其中KN,r=0,1,2,3，则任取x,y,若|x-y|为素数，假设f(x)=f(y),则xy(mod4),于是4|x-y|,这与|x-y|是素数矛盾。故集合A中至少含有4个元素。2. 解：设其中甲买了三种书，因他与其余9个人中每人都至少有一种书相同，所以，甲的三种书中，购买人数最多的一种书不少于4人购买。若购买人数最多的一种书有4人购买，则甲的三种书均为4人购买，其他9人的每种书也均为4人购买。因而，10人买书的总数是4的倍数，即4|30，矛盾。于是，购买的人最多的一种书至少有5人购买。考虑下面的购买方式：B1, B2, B3, B1, B2, B4, B2, B3, B5, B1, B3, B6, B1, B4, B5, B2, B4, B6, B3, B4, B5, B1, B5, B6, B2, B5, B6, B3, B4, B63. 解：设已知数列为a1,a2,an。考察下面的排列：a1,a2,a3,a4,a5,a6,a11, a2,a3,a4,a5,a6,a7,a12, a3,a4,a5,a6,a7,a8,a13, , a7,a8,a9,a10,a11,a12,a17,由题设条件，每一横行之和为正数，故表中所有数之和为正数。另一方面，每一列的数之和为负数。将所有列的数的和相加，其和为负，既又得到表中所有数之和为负数。矛盾，故这样的数列最多能有16项。下面我们构造一个有16项的满足条件的数列：5,5,-13, 5,5,5, -13,5,5, -13,5,5,5, -13,5,5。综上可知，满足题中要求的数列最多有16项。4. 解：（1）设各组所含点数为x1,x2,x83,则x1+x2+x83=1994,且m(G)=C3x1+ C3x2+ C3x83 ,(*)若x1-x2 >1则将第一组的一个点移到第二组.因为<0,m(G)将减小。所以在m(G)最小时，每两个xi的差1，因1994=83×24+2=24×81+2×25，故符合条件的使m(G)最小的每组法只有一种：81组各含24点，二组各含25点，这时，m0=81C324+2C325=168544 （2）对25点的组染色如下：将点分为5组：y1,y2,y3,y4,y5,每组5点；每组线段按图（A）染a,b二色；不同组间的连线，按图（B）染另二色c,d。这样染色，没有同边三角形。至于24点的组，只须从25点的组中去掉一点以及连结它的所有线段即可，当然也不会有同色边的三角形出现。 图（A） 图（B）5. 解：考虑mxm的正方形，设xi是第i行中适合条件的小方格的中心的数目，则。如果在某行标出某两个方格的中心，那么在另外任何一行不能标相同列的一对方格。在第I行有对标出的方格。又因为每行标出的方格对不同，故有 ，从而故m(m-1)+k，解得 K,当m=7时，k21,K的最大值为21，如图：*6. 解：令x1,1=x2,1=x3,1=x4,1=x5,2=x6,2=x7,2=x8,2=0,x97,25=x98,25=x99,25=x100,25=0,其余元素为，则每行25个数之和为0+24×=1，此时在表1中每列元素恰有4个为0，因而调整为表二后最后四行全为0，但前96行的数全为，每行之和为1。这说明最小的K97.以下证明K的最小值时97。因为后三行（第98，99，100行）只能容纳75个元素，所以表一中必定有某一行（设为第r行），它的全部25个元素，在调整后的表二中处于前面97行中。否则每行至少有一个元素落入后三行，则至少有100个元素落入后三行，这不可能。这说明在表二中，x97,jxr,j(xr,j仍在表二中的第j列，行数不一定是r。但行号97。）从而对任意i97，有xi,j x97,j xr,j。所以当i97时，。故K的最小值是97。7