高中数学竞赛专题讲座---离散极值.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=19811987,且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达到最大值。设n1n2n30为使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 n1 n2。所以当用n ，n代替 n1，n2时，将使S变大，矛盾。（2）使ni+1-ni=2的i值至多一个。若有1iojo29，使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。故知n1n2n30中，相邻两数之差恰有一个为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排，至少可坐16113=2093人，当然能坐下全部学生1990人。下面我们来看12排座位能否安排下全部学生。注意，这时共有19912=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排空位不超过3211=352个，所以至少已坐了1837人，全部中学生中至多还有1990-1837=153人没坐下，当然可将他们安排在第12排就坐。可见，只要有12排座位，即可使全部学生按要求就坐。最后，让我们来看，只有11排座位情形如何？这时，只有199个空位，要想安排下全部学生，每排空位平均不能达到19个。现设n=80，前79所学校各有25人，最后一个学校有15人，则2579+15=1990。除了一排可以安排25715=190人就坐之外，其余10排至多安排175人，故11排至多安排19017510=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（1ijk）。求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（1ijk），所以Ai-a，b两两不交（i=1，2，3），上述Ai-a，b表示差集：A-B=xxA且xB。但Ai-a，b=3（i=1，2，3），于是S332=11，矛盾。（2）对S的任意一个元素a，A1，A2，Ak至多有三个集合包含a。设已有A1a，A2a，A3a，若AiAj=1（1i1则将第一组的一个点移到第二组.因为0,m(G)将减小。所以在m(G)最小时，每两个xi的差1，因1994=8324+2=2481+225，故符合条件的使m(G)最小的每组法只有一种：81组各含24点，二组各含25点，这时，m0=81C324+2C325=168544 （2）对25点的组染色如下：将点分为5组：y1,y2,y3,y4,y5,每组5点；每组线段按图（A）染a,b二色；不同组间的连线，按图（B）染