第28讲组合几何初步

1、第28讲 组合几何初步组合几何学中尚未解决的难题比比皆是，解决这些问题需要新思想与新方法. 组合几何学是有志挑战数学难题者一展身手的最佳领域之一。 J.帕赫知识方法扫描组合几何是组合数学的一个分支，它研究有限几何图形的如下问题：存在性问题；计数问题；最值问题；位置问题。 1如果要说明一个图形不存在的理由，一般要用到反证法。2如果要说明一个图形存在，一般要用到从极端考虑，局部调整，有序化等数学思想方法，抽屉原理也是常用的工具，有时还需要用构造法将这样的几何图形构造出来。3当满足某些条件的几何图形存在时，需要计算此类几何图形的个数，这就是计数问题。计数问题常用到穷举法，分类讨论，分步计算，容斥原理

2、等方法。4当满足某些条件的几何图形很多时，需要研究何时它具有最优的的性质，如距离最小，面积最大等。有一类最值问题是用估算-证明-构造的方法来处理的。以最大值为例，先依据有限的数据或图形来估计，猜测出这个最大值，然后证明它的取值不会超过这个值，最后构造一个图形说明这个值是可以达到的，这样就证明了这个值就是最大值。5覆盖问题是一类涉及到两个图形位置关系问题，要说明图形A能被图形B覆盖，就是要说明A中任意一点都在B的内部。经典例题解析例1（2004年天津市初中数学竞赛试题）在正2004边形A1A2A2004的各顶点上随意填上1，2，3，501中的一个数，试证明一定存在四个顶点满足如下的条件：（1）以

3、此顶点的四边形为矩形；（2）此四边形相对两顶点所填数之和相等。证明 （1）由题意知，顶点Ai与Ai+1002为一组关于中心对称的两点，其中i=1,2, ，1002,则2004个顶点可分为1002组。 顺次连结每两组的顶点，可得到一个四边形，由于其对角线互相平分且相等，所以得到的四边形是矩形。 （2） 设在顶点Ai上所填的数字是ai, 则2ai+ ai+10025012=1002，即2到1002共有1001个不同的数。又1002组顶点有1002个数，由抽屉原理知，至少有两组顶点所填数之和相等，则此两组顶点即为所求的四个顶点。例2（1996年汉城国际数学邀请赛中国集训队试题）如图，ab,直线a上有

4、十个点：A1，A2，A10；直线b上有九个点：B1，B2，B9。将a上的每一个点与b上每一个点相连，可以得到许多线段，已知没有三条线段交于一点，问这些线段一共有多少个交点？解 在a,b上各取两点，四点确定唯一的一个交点。从a上取两点有1092=45种方法，从b上取两点有982=36种方法，一共有4536=3240种方法。例3（第8届华罗庚杯金杯数学邀请赛决赛试题）周长为100，边长为整数的等腰三角形共有多少种？解 设a,b,c为三角形三边的长，第一种情况,a=bc,这时有c=100-2a,于是，解得25a, 所以共有8种；第二种情况，ab=c , 这时有 a=100-2c,于是,解得c,所以共

5、有16种。综上，两种情况共计24种。例4 （1985年中国科技大学少年班入学考试复试试题）在平面上随意给出了1000万个点，试问能否用一条直线把它们隔开，使得此直线的两侧各有500万个点？解 在连结这1000万个点中任意两点的线段中，必然有两点的距离是最大的，设这两点为M，N。以M为圆心，大于MN的长度为半径作圆，则这1000万个点都在圆的内部。又因为过这1000万个点中任意两点的直线是有限的，故我们可以在圆外作一条直线l，使得它与过这1000万个点中任意两点的直线都不平行。这样一来，这1000万个点都位于直线l的一侧，且到直线l的距离均不相等。设它们到直线l的距离由小到大依次为d1,d2,d

6、, 记与直线l的距离为di的点为Bi(i=1,2, ，).作直线ml，使直线m与l的距离为d, 其中dd d,则m的两侧各有500万个点。例5（2002年上海市初中数学竞赛试题）平面上有7个点，它们之间可以连一些线段，使7点中的任意3点必存在2点有线段相连。问至少要连多少条线段？证明你的结论。解 （1）如果某点A不作为线段的端点，则其它6点每两点都有线段相连，共要连65=15条线段；（2）如果点A只作为1条线段的端点，则不与A相连的5点之间每两点都有线段相连，至少要连54=10条线段，共要连11条线段；（3）若每一点至少作为两条线段的端点若点A只作为两条线段AB、AC的端点，则不与A相连的4点

7、之间每两点都有线段相连，至少要连43=6条线段。从B至少还要引出一条线段，所以这时至少有2+6+1=9条线段（4）若每一点至少作为两条线段的端点则至少要要连73条线段。注意到线段的条数为整数，故此时至少要连11条。右图表明9条线段已经足够了例6（1979年北京市初中数学竞赛试题）平面上有n个不同的点，每一对点连结成一条线段。将每一条线段的中点涂上红色。（1）证明：平面上红色点的个数不小于2n-3；（2）请你设计一种特殊的情况，使得涂上红色的点的个数等于2n-3。解 （1）在所有的点中，找出距离最大的两点M和N，设它们的距离为d。分别以M，N为圆心，d为半径作圆CM ，圆CN（如图）。在余下的n

8、-2个点中，对于任何一个点P来说，由于MPMN,因此MP的中点必在圆CM内（或圆周上），同理，NP的中点必在圆CN内（或圆周上）。于是在。圆CM，CN内至少各有n-2个红色的点，再加上MN的中点（即两圆的切点），平面上至少有2n-3个红色的点。（2）当n个点全部都在一条直线上，并且相邻两点间的距离都相等时，涂上红色的点的个数等于2n-3。如下图中的n个点A1，A2，An中，A1A2=A2A3=An-1An。 显然每对相邻点所成线段的中点应该涂成红色，共得n-1个红点，此外除A1，An两点外。其余A2，An-1这n-2个点也至少是某一条线段AiAj的中点，这n-2也应涂成红色，因此恰有2n-3个

9、红色的点。例7（1992年湖北省黄冈地区初中数学竞赛试题）已知一个凸多边形不能覆盖任何面积为1的三角形。证明:这个凸多边形可以被面积为4的三角形覆盖住。证明 如图，设凸多边形为Q，则Q的各顶点连成的三角形中可以找到面积最大的一个，不妨设其为ABC，显然SABC1.过A作直线lBC, 过B作直线mCA, 过C作直线nAB, 直线l,m,n相交得到ABC. 则有SABC=4.SABC4.下面证明ABC.能盖住凸多边形Q。如若不然，将存在Q的点P在ABC的外部，连结PB，PC，PBC的面积就大于ABC的面积，这与ABC的面积为Q中的最大三角形的面积相矛盾。所以这个凸多边形可以被ABC 覆盖住，而SA

10、BC.4.例8（1998年湖南省高中理科实验班招生考试试题）将四个圆面Ck（k=1，2，3，4）叠置起来，使得其中任何三个都有公共点。若设C1，C2，C3有公共点P，C1，C2，C4有公共点Q，C1，C3，C4有公共点R，C2，C3，C4有公共点S，那么这四个圆面是否有公共点？并证明你的结论。解 这四个圆面有公共点，下面对P，Q，R，S的三种位置关系讨论如下：(1)若P,Q,R,S四点共线，不妨设S，P在线段QS上（如图）因P，Q都在C1，C2内，故线段PQ也在C1，C2内，于是线段SP也在C1，C2内；同理，线段SP也在C3，C4内，即四个圆面有公共的线段SP。 (2) 若P,Q,R,S四点

11、不共线，这时又可分为两种情况： 这四点是一个凸四边形的四个顶点（如图）仿（1）可证线段PQ在C1，C2内，线段SR在C3，C4内，于是它们的交点M就同时在四个圆面内了这四点不是一个凸四边形的四个顶点，这时必有一点在其余三点所成的三角形的内部或边上，不妨设S在PQR的内部或边上（如图）因P，Q，R三点都在C1内，故PQR在C1内，于是点S在C1内。 但S又同时在C2，C3，C4内，于是四个圆有公共点S。同步训练一 选择题1（1993年浙江省初中数学竞赛试题）把一根长为100厘米的铁丝截成n小段（n3）每段不小于10厘米，若对不论怎样的截法，总存在3小段，以它们为边可以拼成一个三角形，则n的最小值

12、是（ ）(A) 3 (B) 4 (C) 5 (D) 62将一个圆形纸片用直线划分成大小不限的若干小纸片，如果分成的小纸片不少于2004，那么至少要划的直线的条数是（ ）（A）61（B）62（C）63（D）643（1994年浙江省初中数学竞赛试题）凸五边形的各边长均为整数，最大边长为26，最小边长为2，其他三条边中没有两条边相等，则五边形的第二大边的长至少等于（ ）（A）11 （B）10 （C）9 （D）84（1997年山东省初中数学竞赛试题）已知周长小于15的三角形三边的长都是质数，且其中一边的长为3，这样的三角形有（ ） (A) 4 个 (B) 5 个 (C) 6 个 (D) 7 个5（19

13、89年“祖冲之杯”初中数学邀请赛试题）把一个333的正方体的每一个面（共六个面）都等分成大小相同的9个正方形（共54个小正方形）。现用红黄蓝三种颜色去涂这些小正方形，使得有公共边的小正方形不同颜色，那么可以涂成红色的小正方形最多有（A） 28个 （B） 27个 （C） 22个 （D） 20个二 填空题6（2002年“五羊杯”初三数学竞赛试题）平面上n条直线，它们恰有2002个交点，n的最小值是 。7（1992年第九届缙云杯初中数学邀请赛试题）把n3个棱长为1的小正方体拼成一个棱长为1的大正方体,然后给大正方体各面涂色。若恰有一面涂色的小正方体的个数等于各面均未涂色的小正方体个数,则n= .8（

14、2003年湖北省第一届“创新杯”数学邀请赛试题）已知三角形的三边长都是整数，最长边长为8，则满足上述条件的互不全等的三角形的个数为 。9（2000年湖南省高中理科实验班招生考试试题）平面上有n个不同的点，其中任意3点都是一个直角三角形的三个顶点则n的最大值为 。10（1999年第14届江苏省初中数学竞赛试题）在直角坐标系中，已知点A(0，0)，B(0，1)，C(0，2)，D(1，0)，E(2，0)，F(1，1)，G(1，2)，H(2，1)，K(2，2)，则点A，B，C，D，E，F，G，H，K中以其中四点为顶点的正方形有 个，以其中三点为顶点的直角三角形有 个。三、 解答题11（2003年第14

15、届“希望杯”数学邀请赛试题）两条直线上各有n个点，用这n对点按如下规则连结线段：同直线上的点之间不连结；连结的任意两条线段可以有共同的端点，但不得有其它的交点。（1）画图说明当n=1，2，3时，连结的线段各有多少条？（2）由（1）猜想n（n为正整数）对点之间连结的线段最多有多少条，证明你的结论。（3）当n=2003时，所连结的线段最多有多少条？12（1990年武汉市重点中学高一数学竞赛试题）在平面内给定点集A=A1，A2，An，其中任意三点不共线，证明存在n-1条平行线，将平面分割成个n个部分，每一部分包含且仅有集合A中的一个点，且A的点都不在平行线上，试问这样的分割法是否唯一？13（1994年第5届希望杯数学邀请赛试题）(1)现有一个19的“模板”，请你设计一种办法，只用这个“模板”和铅笔在纸上画出1的角来(2)现有一个17的“模板”与铅笔，你能否在纸上面画出一个1的角来(3)现有一个21的“模板”与铅笔，你能否在纸上面画出一个1的角来14（2001年重庆市初中数学竞赛决赛试题）把四边形的任何一边向两方延长，如果其它各边都在延长线的同侧，这