组合最值与操作问题.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 （1）这时分别有：a1+a2+am2+4+2m=m(m+1) （2） b1+b2+bn1+3+(2n-1)=n2 (3)由,得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）。（1）另一方面，显然有=2（n2+1）。由柯西不等式有（）22n（），4（n2+1）22n（n2+1） （2）（2）与（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）染另二色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证明：现将n号卡片按操作移向第一个位置，不难知道，至多移动n-1次后，n号卡片将到达第1个位置，而剩下的n-1张卡片中，同理有：n-1号卡片之多经过n-2次操作后可到达第2位，2号卡片至多经过1次操作，可到达第n-1位。故至多操作次后，卡片将按从大到小顺序排列。2009年全国高中数学联赛模拟试题华南师大附中 李兴怀第一试一、填空题（每小题7分，共8个小题，满分56分）1、已知集合，且是一个单元素集，则实数a的取值范围是_。2、对任意实数x，函数的值都是非负实数，则实数a的取值范围是_。3、不等式的解集是_。4、已知函数，若常数，在区间上是增函数，则的取值范围是_。5、P为椭圆在第一象限上的动点，过点P引圓的两条切线PA,PB，切点分别为A,B。直线AB与x轴、y轴分别交于点M,N，则的面积的最小值是_。6、空间有四个球，它们的半径分别为2，2，3，3，每个球都与其余三个球相切，另有一个小球与这四个球都外切，则这个小球的半径为_。7、设正四面体的四个顶点是A,B,C,D，各棱长度为1米，有一个小虫从A点开始按以下规则前进：在每一个顶点处用同样的概率选择通过这个顶点的三条棱之一，并一直爬到这个棱的尽头，则它爬了7米以后恰好位于顶点A的概率是_。8、从1，2，1000个任选k个数，若在所选的数中总有三个构成三角形的边长，则k最小值是_。二、解答题9、（本题满分14分）设，求证。10、（本题满分15分）设各项均为正数的数列满足，记，且 对恒成立，求数列的通项公式。11、（本题满分15分）设函数，如果对任意，都有，求实数a的取值范围。第二试 一（本题满分50分）已知数列满足，。求证：对任何正整数n，有。二（本题满分50分）在直角三角形ABC中，ABC 的内切圆O分别与边BC，CA， AB 相切于点D，E，F，连接AD与内切圆O相交于点P，连接BP，CP，若，求证：三（本题满分50分）求所有的素数对（p，q），使得四（本题满分50分）n个点顺次在一条直线上，每个点染上白、红、绿、蓝、紫色中的一种颜色，若对任意相邻的两点，要么这两点同色，要么至少有一点为白色，则称之为好的染法。求好的染法的总数。2009年全国高中数学联赛模拟试题第一试解答一填空题1、解：作出函数的图像，然后讨论直线的位置，由图像可知：当时，是单元集；时，是二元集；时，也是单元集。故所求a的取值范围是。第1题图2、解：由条件知，解得。下面证明：当时，对任意，都有，事实上，记，则，记，当时，当时，结合知；当时，所以当时，总有，故满足条件的a构成的集合为。3、解：由条件知，分三种情形讨论：（1）当时，原不等式变形为，由于在上递增，结合，可知。（2）当，原不等式变形为，记，则，当时，又，所以在时单调递增，又故此时不等式的解集为；（3）当时，原不等式变为，而时，故满足原不等式。故所求不等式的解集为。4、解：，而在上是增函数，故，其中，故，即，从而，故。5、解：设P，则直线AB的方程为，故，当，即P为时等式成立，故的最小值为。第5题图6、解：如图，以四个球的球心为顶点作四面体ABCD，AB=6,CD=4，AC=BC=AD=BD=5，设AB、CD的中点分别为F，E，小球的球心为O，由图形的对称性可知O点在EF上。设小球的半径为r，则，,因为EF=OF+0F，所以，解得，故这个小球的半径为。第6题图7、解：设表示小虫走过n米后又达到A点的概率（n=0，1，2），若小虫爬过n-1米而不在A点，则概率是，而从A外的一点向A爬来的概率是，因此有，又知，可计算得，故所求概率为。8、解：选取15个数：1，2，3，5，8，13，21，34，55，89，233，377，610，987，其中的任三个数均不能组成三角形的三边，所以。设选出的