组合最值与操纵问题

组合最值与操作问题.知识与方法在数学竞赛中，经常有一些与组合问题相关的整最值问题，简称组合最值。所谓组合最值，就是指以整数、集合、点、线、圆等离散对象为背景，求它们满足某些约束条件的极大值或极小值。这类问题的解法与一般函数（连续变量）极值的解法有很大的差异。对于这类非常规的极值问题，要针对具体问题，认真分析，细心观察，选用灵活的策略与方法。通常可以从论证与构造两方面予以考虑。先论证或求得该变量的上界或下界，然后构造一个实例说明此上界或下界可以达到，这样便求得了该组合量的极大值或极小值。在论证或求解组合量的上界或下界时，通常要对组合量做出估计，在估计的过程中，构造法、分类讨论法、数学归纳法、反证法、极端原理、抽屉原理等起着重要的作用。在数学竞赛中，还有一类操作问题。这类问题是指在一定的规则下，对给定的对象进行调整，探求被调整对象的初始状态或终止状态及其变化规律。.范例选讲例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+⋯+am≥2+4+⋯+2m=m(m+1)（2）b1+b2+⋯+bn≥1+3+⋯+(2n-1)=n2(3)由①,②,③得m2+m+n≤1987,因而有（m+1）2+n2≤1987124④由④及柯西不等式，得3（m+1）+4n≤3242.(m1)2n2519871,224由于3m+4n为整数，所以3m+4n221,⑤另一方面，当m=27,n=35时，m2+m+n2=1981<1987,且3m+4n=221。故3m+4n的最大值为221。评注：在论证过程中用到了柯西不等式与一般二元一次不定方程的求解方法。例2．设空间中有2n(n≥2)个点，其中任何四点都不共面。将它们之间任意连接N条线段，这些线段都至少构成一个三角形，求N的最小值。思路分析：通过构造实例，说明 N≥ n2+1，进而证明当 N=n2+1时，若在2n点间连有N条线段，则这些线段至少构成一个三角形。其证明过程可用数学归纳法或反证法或极端原理，在证明过程中要精打细算。解法一：将2n个已知点均分为 S和T两组：S={A，A，⋯，A}，T={B，B，⋯B}。1 2 n 1 2 n现将每对点Ai和Bj之间都连结一条线段 AiBj，而同组的任何两点之间均不连线，则共有 n2条线段。这时，2n个已知点中的任何三点中至少有两点属于同一组，二者之间没有连线。因而这 n2条线段不能构成任何三角形。这意味着 N的最小值必大于 n2。下面我们用数学归纳法来证明：若在 2n个已知点间连有 n2+1条线段，则这些线段至少构成一个三角形。当n=2时，n2+1=5，即四点间有五条线段。显然，这五条线段恰构成两个三角形。设当n=k（k≥2）时命题成立，当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+aj≤2n。于是，所有线段的两个端点所引出的线段条数之和的总数不超过 2n（n2+1）。但在此计数中，Ai点恰被计算了ai次，故有2nai2≤2n（n2+1）。 （1）i12n另一方面，显然有ai=2（n2+1）。由柯西不等式有i12n2n（ai）2≤2n（ai2），i1i12n≥1×4（n2+1）2＞2n（n2+1）（2）ai2i12n（2）与（1）矛盾。从而证明了必有一条线段，从它的两个端点引出的线段数之和不小于 2n+1。不妨设A1A2是一条这样的线段，从而又有Ak（k≥3），使线段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+1≤1［k+k(2n-k)+(2n-k-1)k ］=k(2n-k)≤n2,矛盾，这就完成了2全部证明。评注：本题用了三种方法求解，都是先通过例子确定出 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}也满足条件，则x1≤4，x2≤8，x3≤16，x4≤32，x5≤64。但x4+x5=96﹤100，∴x5=50，x3+x4=48﹤50，∴x4=25x2+x3=24﹤25，∴x3=25，与x3是整数矛盾。2故A的元素个数的最小值是 9。评注：先构造的例子说明集合 A的元素个数的最小值小于或等于9，后论证A的元素个数不可能小于 9，这里运用了反证法。例4．平面上给定n个点A1，A2，⋯，An（n≥3），任意三点不共线。由其中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）+⋯=(n1)(n3)...n2,若为n偶数；14(n1)(n3)...n212,若为n奇数。4另一方面，我们可以把 n个点分成两组：n为偶数时，每组各个点；n为奇数时，一组n1个点，一组n1个点。把第一组的每点2 2 2与第二组的每点连结成 n2或n2 1 条直线，这些直线不相交成三个顶4 4点都是给定点的三角形。所以，当n为偶数时，k的最大值是n24

当n为奇数时，k的最大值是n2 1。4评注：本题在对 K进行估计时，要对 n分奇数，偶数进行讨论。例5空间中有1989个点，其中任何三点都不共线。把它们分成点数各不相同的30组，在任何三个不同的组中各取一点为顶点作三角形。试问要使这种三角形的总数最大，各组的点数应为多少？（1989年全国中学生数学冬令营试题）思路分析：先把 1989个以知点分成个数分别为 n1，n2，⋯，n30的30组，其顶点在三个不同组的三角形总数可表示为S=ninjnk.，然后通过逐步调整法求S的最大值。1i j k n解：设1989个已知点分成30组，各组的点数分别为n1，n2，⋯，n30.因此，顶点在不同组的三角形的总数为S=ninjnk.1ijkn30于是，本题即是问在ni1989且n1，n2，⋯，n30互不相同的条i1件下，S在何时取得最大值。由于把1989个点分成30组只有有限种不同的分法，故必有一种分法使S达到最大值。设n1<n2<⋯<n30为使S达到最大值的各组的点数。（1）对于i=1,2,⋯,29，均有ni+1-ni≤2。若不然，设有i0使30ni0+1-ni0≥3，不妨设i0=1这时我们改写S=n1n2nk+（n1+n2）k3njnk+ninjnk。3jk303ijk30令n11=n1+1，n12=n2-1，则n11<n12<n3，n11+n12=n1+n2，n11 n12= n1 n2 + n2- n1-1> n1 n2。所以当用n11 ，n12代替n1，n2时，将使

S变大，矛盾。（2）使

ni+1

-ni=2的

i

值至多一个。若有

1≤io<j

o≤29，使nIo+1-nIo=2，njo+1-n

jo=2，则当用

n1io=nio+1，n1jo1=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=mj1,j1,2,,io,mj,jio1,,30.其中1≤io≤29。于是有io1)+30j)=1989，(mj(mj1yio130m-io=1524，由此解得m=51，io=6。所以当S取得最大值时，30组点数依次为51，52，⋯，56，58，59，⋯，81。评注：本题运用逐步调整的方法，得到了使 S取最大值的必要条件和充分条件，其间运用了反证法。例6．某市有n所中学，第i所中学派出Ci名学生到体育馆观看球赛（1≤Ci≤39，i=1，2，⋯，n），全部学生总数为nCi=1990。看台上每一横排有 199个座位。要求同一学校的学生必i1须坐在同一横排。问体育馆最少要安排多少横排才能保证全部学生都能坐下？（1990年全国高中数学联赛二试）思路分析：利用 1≤Ci≤39，对每排至少可坐的学生人数或每排至多可留出的空位数进行分析，确定出至少需要的横排数。解：由于1≤Ci≤39，故每一横排至少可坐 161人，于是只要有13排，至少可坐161×13=2093人，当然能坐下全部学生1990人。下面我们来看12排座位能否安排下全部学生。注意，这时共有199×12=2388个座位，坐了1990人后，还有398个座位。因此，如果每排的空位数都不超过 33个，便可安排下全部学生。将所有学校学生从多到少重新编号，于是有C1≥C2≥C3≥⋯≥Cn。这样存在非负整数 m，使Cm≥34而Cm+1≤33。（若m=0，则意味着所有 Ci都不超过33）。设m=5p+r（0≤r﹤5）。将前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×7＋15=190人就坐之外，其余10排至多安排175人，故11排至多安排190＋175×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）｜Ai∩Aj｜≤2（1≤i<j≤k）。求K的最大值。（1994年国家集训队试题）思路分析：应当根据子集满足的条件推导出一个K的上界。作如下试探：令

A1={1，2，3，4，5},

各子集间至多有

2个公共元，令A2={1

，2，6，7，8}，此时，若

{1，2}

A3，则必有｜A1∩A3｜≥3或｜A2∩A3｜≥3矛盾。由此得到第一个猜想：

A1，A2，⋯

Ak中至多有两个集合包含同一个

2元子集。令A={1，3，6，9，10}，此时，若3

1∈A，则此时4

A1

，A，A中除23

1外均至多还有一个元素同时属于 A4，｜A4｜≤4，矛盾。由此得到第二个猜想：S中每一个元素至多属于 A1，A2，⋯，Ak中的3个集合。此时可求得

K的一个上界。解：（1）对

S的任意一个

2元子集{a，b}

S，A1

，A2，⋯Ak中至多有两个集合包含

{a，b}。否则，设有

A1

{a，b}，A2

{a，b}，A3 {a，b}，则由于｜Ai∩Aj｜≤2（1≤i<j≤k），所以Ai-{a，b}两两不交（

i=1

，2，3），上述

Ai-{a

，b}表示差集：

A-B={x｜x∈A且

xB}。但｜

Ai-{a

，b}｜=3

（i=1

，2，3），于是｜S｜≥3×3＋

2=11，矛盾。2）对S的任意一个元素a，A1，A2，⋯Ak至多有三个集合包含{a}。设已有A1{a}，A2{a}，A3{a}，若｜Ai∩Aj｜=1（1≤i<j≤3），则｜A1∪A2∪A3｜=3×4＋1=13，矛盾。设b≠a，且a，b∈A1∩A2，则｜A1∪ A2｜=8，根据（1），b A3且｜A3∩A1｜≤2，｜A3∩A2｜≤2，所以A3中至多还有2个元素不属于A1∪

A2，即

A1

A2

A3。同理，若还有

A4

{a}

，那么

A1

A2

A4，从而｜

A3∩A4｜≥3，矛盾。故对任意

a∈S，a

至多属于

A1

，A2，⋯

Ak中

3个子集，所以S中每个元素至多在｜A1｜ +｜A2｜+⋯ +｜Ak｜中作了3重计数，故｜A1｜+｜A2｜+⋯+｜Ak｜≤3｜S｜=30，所以K≤6。按照上述思路，可构造出符合条件的 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整除的数}，A={S中被7整除的数}，并记A=A∪A∪A∪A，则利用容斥原4 1 2 3 4理计算得|A|=216由于在A中任取5个数必有两个数在同一个 Ai中(i=1,2,3,4) ，且不互素，故 n≥217.另一方面，设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=B∪B∪⋯∪B,则|B|=88，于是S-B含有192个元素。在1 2 6S中任取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个棋子，才可能使得余下的棋子没有五子连珠。例10、对一个正整数操作如下：去掉其个位数，再加上个位数的5倍（如：39?3+9′5=48），问71998能否经过这样有限次操作变为19987？解：设此操作将an变为an+1，un为an的个位数，则an=10tn+un，tn为非负整数。所以an+1=tn+5uno50tn+5un=5(10tn+un)=5an(mod7)，而71998o0(mod7)，19987o3(mod7)。所以不可能由71998变为19987。例11．如图所示，圆形的水池被分割为2n（n≥5）个“格子”。我们把有公共隔墙（公共边或公共弧）的“格子”称为相邻的，从而每个“格子”都有三个邻格。水池中一共跳入了4n+1只青蛙，青蛙难于安静共处，只要某个“格子”中有不少于3只青蛙，那么迟早一定会有其中3只分别同时跳往三个不同邻格。证明：只要经过一段时间之后，青蛙便会在水池中大致分布均匀。所谓大致分布均匀，就是任取其中一个“格子”，或者它里面有青蛙，或者它的3个邻格里都有青蛙。证明：我们把一个格子中出现一次三只青蛙同时分别跳向三个邻格的事件称为该格子发生一次 “爆发”。而把一个格子或者是它里面有青蛙，或者是它的三个相邻的格子里面都有青蛙，称为该格子处于“平衡状态”。容易看出，一个格子只要一旦有青蛙跳入，那么它就一直处于“平衡状态”。事实上，只要不“爆发”，那么该格子中的青蛙不会动，它当然处于“平衡状态”；而如果发生“爆发”，那么它的三个邻格中就都有青蛙，并且只要三个邻格都不“爆发”，那么它就一直处于“平衡状态”；而不论哪个邻格发生“爆发”，都会有青蛙跳到它里面，它里面就一定有青蛙，所以它也一直处于平衡状态。这样一来，为证明题中断言，我们就只要证明：任何一个格子都迟早会有青蛙跳入。任取一个格子，把它称为格A，把它所在的扇形称为1号扇形，把该扇形中的另一个格子称为格B，如图。我们证明格A迟早会有青蛙跳入。ABBA3n3n2121按顺时针方向依次将其余扇形接着编号为 2至n号。首先证明1号扇形迟早会有青蛙跳入。假设 1号扇形中永无青蛙到来，那么就不会有青蛙越过 1号扇形与n号扇形之间的隔墙。我们来考察青蛙所在的扇形编号的平方和。由于没有青蛙进入 1号扇形（尤其没有青蛙越过1号扇形与n号扇形之间的隔墙），所以只能是有 3只青蛙由某个k(3≤k≤n-1)号扇形分别跳入 k-1，k和k+1号扇形各一只，因此平方和的变化量为(k-1)2+k2+(k+1)2-3k2=2即增加2。一方面，由于青蛙的跳动不会停止（因为总有一个格子里有不少于3只青蛙），所以平方和的增加趋势不会停止；但是另一方面，青蛙所在扇形编号的平方和不可能永无止境地增加下去（不会大于(4n+1)n2），由此产生矛盾，所以迟早会有青蛙越过 1号扇形与n号扇形之间的隔墙，进入 1号扇形。我们再来证明1号扇形迟早会有三只青蛙跳入。如果 1号扇形中至多有两只青蛙跳入，那么它们都不会跳走，并且自始至终上述平方和至多有两次变小（只能在两只青蛙越过1号扇形与n号扇形之间的隔墙时变小），以后便一直持续不断地上升，从而又重蹈刚才的矛盾。所以1号扇形迟早会有3只青蛙跳入。如果这三只青蛙中有位于A格的，那么格A中已经有青蛙跳入；如果这3只青蛙全都位于格B，那么格B会发生“爆发”，从而有青蛙跳入格A。.训练题对有限集A，存在函数f:N*→A,具有下述性质：若i,j∈N*,且|i-j| 是素数，则f(i) ≠f(j) ，问集合 A中至少有几个元素？．10人到书店买书，已知（1）每人都买了三种书；（2）任何两人所买的书中，都至少有一种相同。问购买的人数最多的一种书最少有几个人购买？．在一个有限的实数数列中，任何七个连续项之和都是负数，而任何十一个连续项之和都是正数，试问这样的数列最多能有多少项？．给定平面上的点集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每列中的数按由大到小的次序从上到下重新排列为 x’1,j≥x’2,j≥⋯≥x’100,j(j=1,2, ⋯,25), 如表2。求最小自然数K，使得只要表1中填入的数满足25xi,j 1(i 1,2,...,100)，则当i≥K时，在表 2中就能保证j1

25x'i,j 1成立。j 1X1,1X1,2⋯X1,25表1X’1,1X’1,2⋯X’1,25X2,1X2,2⋯X2,25表2X’2,1X’2,2⋯X’2,25⋯⋯⋯⋯⋯⋯⋯⋯XX⋯X’100’100⋯’100100,100,XXX100,,1225,1,2257、有n张卡片，每张卡片上有 1到n中的1个数，且每张卡片上的数不同。n张卡片一字排开，可进行如下操作：即将相邻两张1卡片调换过来。证明：无论卡片如何排列，最多经过 n(n-1)次操作2后，卡片按从大到小顺序排列。四.训练题提示或解答1． 因为1,3,6,8 这四个数字中任何两个数字的差的绝对值均为素数，由题意知

f(1),f(3),f(6),f(8)

是A中四个两两不等的元素。从而|A|

≥4.另一方面，若令

A={0,1,2,3},f:

N*

A的对应关系为：若

x∈

N*

,x=4k+r,

则

f(x)=r,

其中K∈N,r=0,1,2,3

，则任取

x,y

∈

N*,

若|x-y|

为素数，假设

f(x)=f(y), 则x≡y(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,B6}设已知数列为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,则将第一组的一个点移到第二组。因为3Cx1

1

3Cx2

1

3Cx1

3Cx2

3Cx1

1

3Cx2

2Cx2

3Cx1

1

2Cx1

1

3Cx2

2Cx2

2Cx1

<0,m(G)将1减小。所以在

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行中适合条件的小方格的中m心的数目，则 xi k。如果在某行标出某两个方格的中心，那么在i 1另外任何一行不能标相同列的一对方格。在第I行有1xi(xi1)对标2出的方格。又因为每行标出的方格对不同，故有mxi(xi1)m(m1)，从而22i1mmm(x1...xm)2k2xi2m(m1)xim(m1)k，又因为xi2,i1i1i1mm故k2≤m(m-1)+k，解得K1(mm4m3),当m=7时，k≤21,Km2的最大值为21，如图：*********************．令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,其余元素为

1，则每行

25个数之和为

0+24×

1=1，此时在表

1中每24

24列元素恰有

4个为

0，因而调整为表二后最后四行全为

0，但前

96行的数全为

1，每行之和为

25〉1。这说明最小的

K≥97.以下证明24

24K的最小值时97。因为后三行（第 98，99，100行）只能容纳75个元素，所以表一中必定有某一行（设为第 r行），它的全部25个元素，在调整后的表二中处于前面 97行中。否则每行至少有一个元素落入后三行，则至少有 100个元素落入后三行，这不可能。这说明在表二中，x97,j’≤xr,j(xr,j仍在表二中的第 j列，行数不一定是r。但行号≤97。）从而对任意i≥97，有xi,j’≤ x97,j’ ≤xr,j。所以当i≥97时，25xi',j25xr,j1。故K的最小值是97。j1j17．证明：现将n号卡片按操作移向第一个位置，不难知道，至多移动n-1次后，n号卡片将到达第1个位置，而剩下的n-1张卡片中，同理有：n-1号卡片之多经过n-2次操作后可到达第2位，⋯⋯，2号卡片至多经过1次操作，可到达第n-1位。故至多操作n-1?i=1n(n-1)次后，卡片将按从大到小顺序排列。i=1 22009年全国高中数学联赛模拟试题华南师大附中李兴怀第一试一、填空题（每小题7分，共8个小题，满分56分）1、已知集合A={(x,y)|y=ax+2},B={(x,y)|y=|x+1|}，且AB是一个单元素集，则实数a的取值范围是________。2、对任意实数x，函数f(x)=x2-2x-|x-1-a|-|x-2|+4的值都是非负实数，则实数a的取值范围是________。3、不等式|log2x-3|+|2x-8|39的解集是________。4、已知函数)=2px，若常数，y=f(wx)在区fx4sinxsin(+)+cos2xw>0(A42间[-p,2p]上是增函数，则w的取值范围是___________。235、P为椭圆x2+y2=1在第一象限上的动点，过点P引圓x2+y2=9的两条切线169PA,PB，切点分别为A,B。直线AB与x轴、y轴分别交于点M,N，则DMON的面积的最小值是_________。6、空间有四个球，它们的半径分别为2，2，3，3，每个球都与其余三个球相切，另有一个小球与这四个球都外切，则这个小球的半径为___________。7、设正四面体的四个顶点是A,B,C,D，各棱长度为1米，有一个小虫从A点开始按以下规则前进：在每一个顶点处用同样的概率选择通过这个顶点的三条棱之一，并一直爬到这个棱的尽头，则它爬了7米以后恰好位于顶点A的概率是________________。8、从1，2，⋯，1000个任选k个数，若在所选的数中总有三个构成三角形的边长，则k最小值是___________。二、解答题9、（本题满分14分）设n?N*，求证3￡(1+1)n<2。22n10、（本题满分15分）设各项均为正数的数列{an}满足3a1=2,an=an2+1an+2(n?N*)，记bn=a1a2×an，且bn322对n2恒成立，求数列{bn}的通项公式。11、（本题满分15分）设函数f(x)=sinx，如果对任意x30，都有f(x)￡ax，求实数a的取值范2+cosx围。第二试一．（本题满分50分）已知数列{an}满足a1=1，2an=(2n-3)an-1，n=2,3,4,×。求证：对任何正整数nn，有?ak<1。2nk=1二．（本题满分50分）在直角三角形ABC中，ACB与边，，相切于点，，，连接与内切圆BCCAABDEFAD

90，△ABC的内切圆O分别O相交于点P，连接BP，CP，若BPC 90，求证：AE AP PD．三．（本题满分50分）求所有的素数对（p，q），使得pq5p5q．四．（本题满分50分）n个点P1,P2,,Pn顺次在一条直线上，每个点染上白、红、绿、蓝、紫色中的一种颜色，若对任意相邻的两点Pi,Pi1(i1,2,,n1)，要么这两点同色，要么至少有一点为白色，则称之为好的染法。求好的染法的总数。2009年全国高中数学联赛模拟试题

第一试解答一．填空题1、解：作出函数

y=|x+1|的图像，然后讨论直线

y=ax+2的位置，由图像可知：当a31时，

A

B是单元集；

-1<a<1时，

A

B是二元集；

a￡-1时，

A

B也是单元集。故所求

a的取值范围是

(-

￥,-1]

[1,+￥]。第1题图ì=-|1+a|+2302、解：由条件知?，解得-2￡a￡1。í?=-|a|+230?f(1)下面证明：当-2￡a￡1时，对任意x?R，都有f(x)30，事实上，记t=x-1，则f(x)=t2-|t-a|-|t-1|+3，记g(t)=t2+3-|t-a|-|t-1|，当t￡a时，g(t)=t2+3-(a-t)-(1-t)=(t+1)2+(1-a)30当a<t￡1时，g(t)=t2+3-(t-a)-(1-t)=t2+2+a结合a32知g(t)30；当t>1时，g(t)=t2+3-(t-a)-(t-1)=t2-2t+4+a=(t-1)2+3+a33a31+所以当-2￡a￡1时，总有f(x)30，故满足条件的a构成的集合为{a|-2￡a￡1}。3、解：由条件知x>0，分三种情形讨论：（1）当x?(0,3]时，原不等式变形为2x+log2x￡2，由于f(x)=2x+log2x在(0,3]上递增，结合 f(1)=2，可知0<x￡1。2）当x?(3,8]，原不等式变形为2x-log2x314，记g(x)=2x-log2x，则g'(x)=2xln2-1，当x33时，2xln238ln2，1￡1，又xln2xln23ln28ln2-1=ln28-1>0，所以g(x)在x33时单调递增，又3ln2ln8g(4)=24-log24=14故此时不等式的解集为[4,8]；（3）当x>8时，原不等式变为2x+log2x320，而x>8时，2x+log2x>28+log28=259>20，故x>8满足原不等式。故所求不等式的解集为(0,1][4,+￥)。4、解：f(x)=2sinx+1，而f(wx)=2sinwx+1在[-p,2p]上是增函数，故23p,2p]2kp-p2kp+p，故2k-1￡-1w，2k+132w，[-[2,2]，其中k?Z23íww2223即4k￡1-w<1，4k34w-1>-1，从而k=0，故w?(0,3]。345、解：设P(4cos,3sin)，q?(0,p)，则直线AB的方程为qq24xcos+3ysinq=9，q故|OM|=9,|ON|=3,SDMON=1|OM|A|ON|=27327，当4cosqsinq24sin2q4q=p，即P为(22,32)时等式成立，故SDMON的最小值为27。424第5题图6、解：如图，以四个球的球心为顶点作四面体 ABCD，AB=6,CD=4，AC=BC=AD=BD=5，设AB、CD的中点分别为 F，E，小球的球心为 O，由图形的对称性可知 O点在EF上。设小球的半径为 r，则OE= OC2-EC2= (r+2)2-22= r(r+4)，OF= OA2-AF2= (r+3)2-33= r(r+6)EF=AE2-AF2=AD2-DE2-AF2=52-22-32=12,因为EF=OF+0F，所以12=r(r+4)+r(r+6)，解得r=6，故这个小球的半径为6。1111AFODBEC第6题图7、解：设an表示小虫走过 n米后又达到 A点的概率（n=0，1，2⋯⋯），若小虫爬过n-1米而不在A点，则概率是1-an-1，而从A外的一点向A爬来的概率是1，因此有3an=1(1-an-1)，又知a0=1，可计算得a7=182，故所求概率为182。37297298、解：选取 15个数：1，2，3，5，8，13，21，34，55，89，233，377，610，987，其中的任三个数均不能组成三角形的三边，所以 k316。设选出的 16个数a1<a2< ×<a16，若没有三个数构成三角形的三边长，则a131,a232,a33a1+a233,a43a2+a335,×,a153a13+a143987,a163a14+a1531597，这与a16￡1000矛盾，所以选出的 16个数，必有三个数组成三角形的三边，综上， k的最小值为16.二、解答题9、证明：

(11)n=C0+C1(1)+C2(1)2+××+Cr(1)r+×+Cn(1)n+2nnn2nn2nn2nn2n1 n

1

32n又Cnr(1)r2n故

21)(n2)(nr1)1r1rn(n--+=××-A()￡()，r!nr22(11)n11(1)2+××+(1)r+××+(1)n2n22221-(1)n+11222=1=-2n<1-2故3￡(1+1)n<2。22n10．解：由于bn=a1a2××an，则log2bn=log2a1+log2a2+×+log2an令xn=log2an,n=1,2×,Sn表示{xn}的前n项和，则bn=2Sn，由题设x1=1,xn=3xn+1+xn+2,(n?N*)①2Sn=x1+x2+××+xn33(n32)②23，又x1=1，故x231③②式对n=2成立，所以x1+x2322下面用反证法证明：x2￡1。假设x2>1，由①得xn+2+2xn+1=1(xn+1+2xn)222故{xn+1+2xn}是首项为x2+2，公比为1的等比数列，故2xn+1+2xn=1A(x2+2)，n?N*，④2n-1又由①xn+2+1xn+1=-2(xn+1-1xn)，因此{xn+1-1xn}是首项为x2-1，公比212122为-2的等比数列，故xn+1-xn=(-2)n-1A(x2-)，n?N*⑤52112由④-⑤得n-1*xn=(x2+2)An-1-(x2-)(-2)，n?N⑥2225Sn=(x2+2)(2-1(x2-11-(2)n*对n求和得n-1)-)-,n?N⑦2223由题设，知Sn+133，n?N*，且由反证假设x2>1，有2212k)-1)22k+1+115，（这里在⑦中取(x2+2)(2-(x2-33n=2k+1,k31）224从而(x2-122k+1+1-1)-15<2x21，k?N*)3￡(x2+2)(22k4+2246x2322k14对k?N*即不等式x212恒成立，但这是不可能的，矛盾，因此x2￡1，结合③式，x2=1，因此221代入⑦式，Sn=2-11a2=2x2=2-2，将x2=，n?N*，所以bn=2Sn=22n-1。22n-111．解：令g(x)=ax-f(x)，则2cosx+12+3=3(11)2+a-1g'(x)=a-+cosx)2=a-2+cosx-，(22+cosx(cosx+2)233故当a31时，g'(x)30，所以g(x)在0,上是增函数，又g(0)=0，所以当3x30时，g(x)3g(0)=0，即f(x)￡ax。当0<a<1时，令h(x)=sinx-3ax，则h'(x)=cosx