组合最值与操作问题.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+…+am≥2+4+…+2m=m(m+1) （2）
b1+b2+…+bn≥1+3+…+(2n-1)=n2 (3)
由①,②,③得m²+m+n2≤1987,因而有（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(n≥2)个点，其中任何四点都不共面。将它们之间任意连接N条线段，这些线段都至少构成一个三角形，求N的最小值。
思路分析：通过构造实例，说明N≥n2+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（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次，故有
≤2n（n2+1）。（1）
另一方面，显然有=2（n2+1）。由柯西不等式有
（）2≤2n（），
≥×4（n2+1）2＞2n（n2+1） （2）
（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≤［k+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}也满足条件，则x1≤4，x2≤8，x3≤16，x4≤32，x5≤64。
但x4+x5=96﹤100，∴ x5=50，
x3+x4=48﹤50，∴x4=25
x2+x3=24﹤25，∴x3=，与x3是整数矛盾。
故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）+…
=
另一方面，我们可以把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-ni≤2。若不然，设有i0使ni0+1-ni0≥3，不妨设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值至多一个。若有1≤io<jo≤29，使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=
其中1≤io≤29。于是有
+=1989，
30m-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），全部学生总数为=1990。看台上每一横排有199个座位。要求同一学校的学生必须坐在同一横排。问体育馆最少要安排多少横排才能保证全部学生都能坐下？（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元子集。令A3={1，3，6，9，10}，此时，若1∈A4，则此时A1 ，A2，A3中除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），bA3且｜A3∩A1｜≤2，｜A3∩A2｜≤2，所以A3中至多还有2个元素不属于A1∪ A2，即 A3。
同理，若还有A4{a}，那么 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整除的数}，
A4={S中被7整除的数}，并记A=A1∪A2∪A3∪A4，则利用容斥原理计算得|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=B1∪B2∪…∪B6,则|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个棋子，才可能使得余下的棋子没有五子连珠。
例10、对一个正整数操作如下：去掉其个位数，再加上个位数的5倍（如：），问能否经过这样有限次操作变为？
解：设此操作将变为，为的个位数，则，为非负整数。所以，而， 。所以不可能由变为。
例11．如图所示，圆形的水池被分割为2n（n≥5）个“格子”。我们把有公共隔墙（公共边或公共弧）的“格子”称为相邻的，从而每个“格子”都有三个邻格。
水池中一共跳入了4n+1只青蛙，青蛙难于安静共处，只要某个“格子”中有不少于3只青蛙，那么迟早一定会有其中3只分别同时跳往三个不同邻格。
证明：只要经过一段时间之后，青蛙便会在水池中大致分布均匀。
所谓大致分布均匀，就是任取其中一个“格子”，或者它里面有青蛙，或者它的3个邻格里都有青蛙。
证明：我们把一个格子中出现一次三只青蛙同时分别跳向三个邻格的事件称为该格子发生一次“爆发”。而把一个格子或者是它里面有青蛙，或者是它的三个相邻的格子里面都有青蛙，称为该格子处于“平衡状态”。
容易看出，一个格子只要一旦有青蛙跳入，那么它就一直处于“平衡状态”。事实上，只要不“爆发”，那么该格子中的青蛙不会动，它当然处于“平衡状态”；而如果发生“爆发”，那么它的三个邻格中就都有青蛙，并且只要三个邻格都不“爆发”，那么它就一直处于“平衡状态”；而不论哪个邻格发生“爆发”，都会有青蛙跳到它里面，它里面就一定有青蛙，所以它也一直处于平衡状态。
这样一来，为证明题中断言，我们就只要证明：任何一个格子都迟早会有青蛙跳入。
任取一个格子，把它称为格A，把它所在的扇形称为1号扇形，把该扇形中的另一个格子称为格B，如图。我们证明格A迟早会有青蛙跳入。

按顺时针方向依次将其余扇形接着编号为2至n号。首先证明1号扇形迟早会有青蛙跳入。假设1号扇形中永无青蛙到来，那么就不会有青蛙越过1号扇形与n号扇形之间的隔墙。我们来考察青蛙所在的扇形编号的平方和。由于没有青蛙进入1号扇形（尤其没有青蛙越过1号扇形与n号扇形之间的隔墙），所以只能是有3只青蛙由某个k(3≤k≤n-1)号扇形分别跳入k-1，k和k+1号扇形各一只，因此平方和的变化量为

即增加2。一方面，由于青蛙的跳动不会停止（因为总有一个格子里有不少于3只青蛙），所以平方和的增加趋势不会停止；但是另一方面，青蛙所在扇形编号的平方和不可能永无止境地增加下去（不会大于），由此产生矛盾，所以迟早会有青蛙越过1号扇形与n号扇形之间的隔墙，进入1号扇形。
我们再来证明1号扇形迟早会有三只青蛙跳入。如果1号扇形中至多有两只青蛙跳入，那么它们都不会跳走，并且自始至终上述平方和至多有两次变小（只能在两只青蛙越过1号扇形与n号扇形之间的隔墙时变小），以后便一直持续不断地上升，从而又重蹈刚才的矛盾。所以1号扇形迟早会有3只青蛙跳入。
如果这三只青蛙中有位于A格的，那么格A中已经有青蛙跳入；如果这3只青蛙全都位于格B，那么格B会发生“爆发”，从而有青蛙跳入格A。
三.训练题
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每列中的数按由大到小的次序从上到下重新排列为x’1,j≥x’2,j≥…≥x’100,j(j=1,2,…,25),如表2。
求最小自然数K，使得只要表1中填入的数满足，则当i≥K时，在表2中就能保证成立。

X1,1
X1,2
…
X1,25
X2,1
X2,2
…
X2,25
…
…
…
…
X100,1
X100,2
…
X100,25
X’1,1
X’1,2
…
X’1,25
X’2,1
X’2,2
…
X’2,25
…
…
…
…
X’100,1
X’100,2
…
X’100,25
表1 表2

7、有n张卡片，每张卡片上有1到n中的1个数，且每张卡片上的数不同。n张卡片一字排开，可进行如下操作：即将相邻两张卡片调换过来。证明：无论卡片如何排列，最多经过次操作后，卡片按从大到小顺序排列。

四.训练题提示或解答
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,其中K∈N,r=0,1,2,3，则任取x,y∈,若|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}
3.设已知数列为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时，k≤21,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。这说明最小的K≥97.以下证明K的最小值时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时，。故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，其中的任三个数均不能组成三角形的三边，所以。设选出的16个数，若没有三个数构成三角形的三边长，则，这与矛盾，所以选出的16个数，必有三个数组成三角形的三边，综上，k的最小值为16.
二、解答题
9、证明：

又，
故

故。
10．解：由于 ，则
令表示的前n项和，则，由题设①
②
②式对n=2成立，所以，又，故③
下面用反证法证明：。假设，由①得
故是首项为，公比为的等比数列，故，，④
又由①，因此是首项为，公比为-2的等比数列，故，⑤
由④-⑤得，⑥
对n求和得⑦
由题设，知，，且由反证假设，有，（这里在⑦中取）
从而，
即不等式对
恒成立，但这是不可能的，矛盾，因此，结合③式，，因此，将代入⑦式，，，所以。

11．解：令，
则，
故当时，，所以在上是增函数，又，所以当时，，即。
当时，令，则，
故当时，，因此，在上单调递增，故当时，即
于是当时，。
当时，有，因此，a的取值范围是。

第二试解答

一、 证明：由假设可知，且对一切正整数，
即
于是

由此可得。
二、证明： 设AE = AF = x，BD＝BF＝y，CD＝CE＝z，AP＝m，PD＝n．
因为，所以．

延长AD至Q，使得，连结BQ，CQ，则P，B，Q，C四点共圆，令DQ＝l，则由相交弦定理和切割线定理可得
， ①
． ②
因为∽，所以，故
． ③
在Rt △ACD和Rt △ACB中，由勾股定理得
， ④
． ⑤
③－②，得 ， ⑥
①÷⑥，得 ，
所以 ， ⑦
②×⑦，结合④，得 ，
整理得 ． ⑧
又⑤式可写为 ， ⑨
由⑧，⑨得