第4讲 组合几何 长沙市一中 申东

2011年协作体夏令营系列讲座(四)

组合几何

长沙市一中 申东

组合几何是一门新兴的数学分支，是组合数学与几何学相结合的产物，它研究的是几何元素的组合问题．例如，“几何计数”、“距离”、“覆盖”等．由于其内容丰富多彩，技巧性强，因而在数学竞赛中颇受欢迎，本讲介绍组合几何中的一些基本问题．

例1．设n为大于等于1的整数，在xy平面上由(0,0)到(n,n)的一条“路”是一条折线，这条折线从（0，0）开始每次或者向右（记为E）或者向上（记为N）运动一个单位，直到到达(n,n)．所有运动都在满足x?y的半平面内进行．在一条“路”中形如EN的两个相邻的运动称为一“步”．证明：从(0,0)到(n,n)恰有s步(n?s?1)的路有Cn?1Cn条．

s1s?1s?1

例2．已知空间中9点，其中任意4点不共面．在这9点间连接若干条线段，使图中不存在四面体，问图中最多有多少个三角形？

例3．平面上不在同一直线上的4点构成矩形的顶点的充要条件是以其中任意三点为顶点的两个三角形均全等．

例4．试确定在平面上是否存在满足下述条件的两个不相交的无限点集A和B： （1）在A?B中，任何三点都不共线，且任何两点的距离至少是1； （2）任何一个顶点在B中的三角形，其内部都存在一个A中的点，

例5．在凸100边形内部，有k个给定点，2?k?50．求证：可以从这凸100边形中选择2k个顶点，以这2k个顶点为顶点作一个2k边形，使得这给定的k个点全部落在这2k是边形内部．

例6．一张平面被两族平行直线划分为单位正方形，考查由所分成的单位正方形成的n?n的正方形．将其中至少有一条边位于n?n正方形边界上的所有单位正方形的并集称为这n?n正方形的边框．给定一个100×100的正方形，求证：恰有一个方法，利用50个正方形的不重叠的边框就能覆盖它．

例7．5?7棋盘用特利米诺角片覆盖，角片不许超出棋盘外，但可彼此交叠，问：能不能找到一种覆盖方法，使得每个小方格上面所盖的特利米诺角片个数都相同?

（讲座四）1

练习题

1：设n和k是正整数，S是平面上n个点的集合，满足条件：对S中每一个点P，S中存在k个点与P距离相等，证明k?12?2n．

2：圆周上有n(n?4)个点，每两点连一条弦，如果没有3条弦交于一点（端点除外），问：

（1）这些弦在圆内一共有多少个交点？ （2）这些弦把图分成多少个区域？

3．平面上给出n(n?3)条直线，其中任意两条不平行，任何3条不共点，证明：在这些直线将平面划分面三角形的部分中，三角形的个数不少于

23(n?1)．

4：平面上已给998个点，将连接每两点的线段中点染成红色，证明：至少有1993个红点．能否找到一个恰有1993个红点的特例？

5：在平面上任意取6个互不相同的点，证明：在两两连接这些点所得的线段中，最长线段与最短线段之比?6?3．

6：把正三角形ABC各边n等分，过各分点在三角形内作边的平行线段将?ABC完全分割成边长为

1nBC的小正三角形．求其中边长为

1nBC的小菱形个数．

（讲座四）2

讲座四 参考答案 2011-7-19

（1）若从A1引出5条边A1A2，A1A3，??，A1A6，则依题意，由于没有四面体，那么，由A2，A3、?，A6这5个点组成的子图中没有三角形．由结论（*），这子图中至多有[条边，那么，以A1为顶点的三角形至多有6个，矛盾．

（2）若从点A1引出6条边A1A2，A1A3，?，A1A7，则类似（1），至多有[角形以A1为顶点，矛盾．

（3）若从点A1引出7条边A1A2，A1A3，?，A1As，由于没有四面体，可知A2,A3?，

A8这7个点构成的子图中没有三角形．再利用结论(?)，这个子图至多有[72

例1．证：将一条从(0,0)到(n,n)有s步的路称为(n,s)型路．设f(n,s)表示(n,s)型的路的数目，g(n,s)?s?1,2,?,n．

524]?61sCn?1Cns?1s?1，我们对n用数学归纳法证明f(n,s)?g(n,s)，

624]?9个三

显然有f(1,1)?1?g(1,1)，f(2,1)?1?g(2,1)，f(2,2)?1?g(2,2)． 当n?2时，假设f(m,s)?g(m,s)，其中1?s?m?n，易知 f(n?1,1)?1?g(n?1,1)．

下面证明f(n?1,s?1)?g(n?1,s?1)，其中1?s?n．

我们称一条(n,s)型路和一条(n?1,s?1)型路相关联，如果(n?1,s?1)型路可以由

(n,s)型路通过将EN插在两个形如EE，NN，NE的相邻运动之间，或通过将EN加在这

4]=12条边．从

而，以A1为顶点的三角形至多有12个，不以A1为顶点的三角形必以点A9为一个顶点，类似地也至多有12个三角形．那么，三角形总数?12?2?24?28，矛盾．

（4）若从点A1引出8条边A1A2，?，A1A9，则此时A2，A3，?，A9这8个点构成的子图中没有三角形．由结论（*），至多有[82条路的两端获得；称一条(n,s?1)型路和一条(n?1,s?1)型路相关联，如果(n?1,s?1)型路可以由(n,s?1)型路通过将EN插在EN之间获得．

每条(n,s)型路与2n?1?s条不同的(n?1,s?1)型路相关联，每条(n,s?1)型路恰与s?1条不同的(n?1,s?1)型路相关联，每条(n?1,s?1)型路恰与s?1条(n,s)型路或

(n,s?1)型路相关联．所以，有(s?1)f(n?1,s?1)?(2n?1?2)f(n,s)?(s?1)f(n,s?1)．

4]?16条边，从而原图中至多有16个三角形，

容易验证(s?1)g(n?1,s?1)?(2n?1?s)g(n,s)?(s?1)g(n,s?1)． 所以，f(n?1,s?1)?g(n?1,s?1)．

例2．解：先证明下述结论

（*）在一个n个点的空间图中不存在三角形，则其边数不超过[n2矛盾．于是，满足题目条件的三角形至多27个．

例3．证：必要性显然，下证充分性．

设平面上4点为A，B，C，D，考虑点集{A,B,C,D}的凸包．若凸包为三角形，不妨设为?ABC，则D为?ABC的内部或边上的点，此时?ABC与?ABD（或?BCD或

，矛盾．由此，凸包为四?CAD）不全等（因两者面积不等）

边形，不妨设凸包为四边形ABCD，如图，因为?ABD与?ABC全等，故S?ABD?S?ABC，所以D，C到直线AB的距

离相等，由此DC//AB．同理有AD//BC．所以?ABCD为

平行四边形，再由?ABD与?ABC全等，知AC?BD．故平形四边形ABCD是矩形．

例4．解：这样的点集不存在，下面用反证法证明． 假设存在这样的点集A和B，则下述命题存在：

对任意自然数n?3，存在这样的凸多边形，它的顶点为标定点（即A?B中的点），而它的内部及边界上共有n个标定点．

事实上，任意取n个标定点，设它们的凸包为P1P2?Pm．由于任意3个标定点不共线，

4]．

设这n个点为A1,A2，?，An，其中从A1引出边数最多，不妨设共有k条边

A1AnA1An?1，?，A1An?k?1．依条件，不存在三角形，那么点An?k?1，?，An之间没有边相

连．从而空间图中每条边均至少有一个端点为A1,A2?，An?k中的点，而每个Ai(1?i?n?k)至多引出k条边，则总边数?k(n?k)?[n24]．

下面证明空间中9点，其中任意4点不共面，在这9点间连接若干条线段，如果图内已有（至少）28个三角形，则至少有一个四面体．

用反证法，假设不存在一个四面体，设这9个点为A1，A2，?，A9．由抽屉原则，其中必有一点为至少[28?39]?10个三角形的顶点，这里[28?39]表示不小于

28?39的最小整

数．从而，从这个点至少引出5条边，设这点为A1．

（讲座四）3

故m?3．因为任何两个标定点的距离至少是1，故以每个标定点为圆心、以

12为半径作圆，

这些圆两两不相交．因此，凸多边形P1P2?Pn内部及边界上只有有限个标定点．设为若k?n，则命题已成立．若k?n，则取P1P2?Pk的凸包Pi1Pi2?Pit，P1P2?Pk，k?1?n ，

其内部及边界上有k?1个标定点．若k?1?n，命题已成立；若k?1?n，则再取

{P2,P3,?,Pk}{Pi}的凸包，这样下去，经k?n次调整，可得一个凸多边形，其内部和边界

1为顶点的凸多边形总数有限，在这有限个这样的凸多边形中，总有面积最小的一个，它就是凸包．因此，不共线点集X总有一个凸包．

如果这k个给定点不全在同一条直线上．依照上面所述，设M?A1A2?An是所给定的k个点的一个凸包，由于点Aj(1?j?n)是属于这k个点组成的集合，所以点Aj(1?j?n)全部在这凸100边形内部．取M内一点O，O不是A1，A2，?，An之一．延长每条线段

OAj(1?j?n)，使它与凸100边形的周界相交于点Bj(1?j?n)．明显地，

上共有n个标定点．

为了进一步证明，我们在上述命题中取n?9，不妨设这时对应的凸多形的内部及边界上的9个标定点中A中的点多于B中的点，分以下两个种情形．

（1）9个标定点中A的点不少于6个，则B中的点不多于3个，取A中的6个点A1，

A2，?，A6．

?OAjAj?1(1?j?n,An?1?A1)包含在?OBjBj?1内，所以M包含在多边形B1B2?Bn内

部．每个点Bj(1?j?n)都在这凸100边形的边上，取出含有这些点Bj(1?j?n)的所有的边，这里边是指凸100边形的边，并考查这些边的端点的集合，该集合中共有m?2n?2k个点，我们再任意地补入这100边形的2k?m个顶点，这样一共得到2k个顶点，以这2k个点为顶点所作成的凸2k边形，它的周界包含全部点B1,B2,?,Bn，因此这凸2k边形包含多边形B1B2?Bn，当然包含M．

如果这k个给定点在同一条直线上，这条直线与凸100边形交于两条边AjAj?1,AiAi?1(1?j?l?99)这是个点必在凸四边形AjAj?1AlAl?1(如果j?1?l)内，或在三角形AjAj?1Aj?2内(如果l?j?1)．再任意补入2k?4或2k?3个凸100边形的顶点，那么这k个给定点必在一个凸2k边形内，这2k边形的全部顶点是这凸100边形的顶点．

例6．证 在所给的100×100的正方形ABCD的两条对角线AC和BD上共分布着200个两两不重叠的单位正方形(两个单位正方形至多可能有一条公共边)．

若其凸包为六边形，不妨设为A1A2?A6，则?A1A2A3，?A1A3A4，?A1A4A5，?A1A5A6中不可能都有B中的点．

若其凸包五边形，不妨设为A1A2?A5，则?A1A2A6，?A2A3A6，?A3A4A5，?A4A1A6中不可能都有B中的点．

若其凸包为四边形，不妨设为A1A2A3A4，则?A1A2A5，?A2A3A5，?A3A4A5，?A4A1A6中不可能都有B中的点．

若其凸包为三角形，不妨设为?A1A2A3，且A5在?A1A2A4的内部，则?A1A2A5，?A2A4A5，

?A1A4A5，?A2A3A4中不可能都有B中的点，矛盾．

（2）9个标定点中有5个A中的点A1，A2，?，A5．

若其凸包为五边形，不妨设为A1A2?A5，则?A1A2A3，?A1A3A4，?A1A4A5中都有一个

B中的点，而以这3个B中的点为顶点的三角形中不可能再有A中的点．

若其凸包为四边形，不妨设为A1A2A3A4，则?A1A2A5，?A2A3A5，?A3A4A5，?A4A1A5中都有一个B中的点，而这4个B中的点的凸包中只可能有一个A中的点，这是不可能的． 若其凸包为三角形，不妨设为A1A2A3，且A5在?A1A2A4内部，则?A1A2A5，?A2A4A5，

?A2A3A4，?A3A1A4中不可能都有B中的点．矛盾．

例5．证给定一个有限点集X，这点集内点不全在同一条直线上．我们将包含这有限点集X的全部点的面积最小凸多边形称为这点集X的一个“凸包”．明显地，对于这点集X，总存在一个多边形，以这点集内一部分(或全部)点为顶点，使得这点集内全部点都落在这多边形的内部或边上(包括顶点上)，且这多边形的每个顶点都属于这点集．如果这多边形是凸的，那么它本身就是凸包．如果这多边形是凹的，那么总可以在它的顶点之间适当添加一些线段，使得有一个凸多边形，其内部或边上包含X内全部点．当然添加连线段可以有许多添法，可以得到许多凸多边形，但由于X是一个有限点集，两点之间连线总数有限．因此，以X内点

而每一个n?n(n??)正方形的边框至多能盖住这200个单位正方形中的4个．题目要求用50个不重叠的正方形的边框盖住这100×100的正方形，那么，满足题目要求的50个正方形的每一个的边框都恰好盖住这200个单位正方形中的4个，即每一个正方形的边框盖住对角线AC上的两个单位正方形，也应盖住对角线BD上的两个单位正方形．

现在证明，正方形ABCD的4个角上的单位正方形一定要为同一个正方形的边框所覆盖．为了方便，我们将一个单位正方形为某个正方形的边框所覆盖，就称这个单位正方形属于这个正方形的边框．如果顶点A和C所在的单位正方形属于同一个正方形的边框K，并且它们位于这边框的相邻的边上，那么这正方形的边框K的这两条边的公共顶点B或D所在的单位正方形也应当属于K．不妨设点B所在的单位正方形属于K，利用正方形边框关于正方形中心的对称性，则点D所在的单位正方形也应当属于这正方形的边框K，因而K盖住对角线BD上两个单位正方形，这两个单位正方形，一个以点B为顶点，一个以点D为顶点．如果顶点A和C所在的单位正方形位于K的两条相对平行的边上，则K的每条边应当由100个单位正方形所组成，所以，顶点B和D所在的单位正方形也应当属于这正方形的边框．最后，我们要指出，点A和点C所在的单位正方形不可能属于两个不同正方形的边框．用反证法，如果点A和点C所在的单位正方形分别属于两个不同正方形的边框，由于这两个正方形

BD上的两个单位正方形，的边框都要盖住对角线．那么，这两个正方形必定有重叠的边框．这

? （讲座四）4

与题目条件矛盾．

这样，要满足题目要求，必有一个正方形的边框盖住顶点A，B，C，D所在的4个单位正方形．由100×100的正方形，去掉这个正方形的边框，得到一个98×98的正方形A?B?C?D，对正方形A?B?C?D进行类似上述的讨论，必有一个正方形的边框，盖住顶点A?B?C?D所在的4个单位正方形，如此继续进行下去，题目结论成立．

例7．解 5×7棋盘的35个小方格，用(i,j)表示位于第i行、第j列的那一格，i?1，2，3，4，5，i?1，2，3，4，5，6，7．第2n?1行与第2m?1行(规n?0,1,2；m?0,1,2,3)

nn2ai2n因此2C?2n?Ci?1，即?ai??ai?2n(n?1)．

i?1n2i?1由柯西不等式，?ai?i?11nn2n2n2(?ai)，所以(?ai)?n(?ai)?2n(n?1)?0．

i?1i?1i?1n解得?ai?(i?112?2n?74)n．

n的交叉处(2n?1,2m?1)格，填写上“?2”，其余的方格中都填写上“+1”．易知，任意一张特利米诺角片盖住的3个小方格中的3个数之和必非负．如果存在符合要求的覆盖，每个小方格都被k张特利米诺角片所盖住，那么

35k3又因为每点可出现在若干个圆上，故?ai?nk，因此k?i?112?2n?74?12?2n．

这张特利米诺角片所盖住的小方格中诸数之和

2. (1)圆上每4个点构成一个凸四边形，它的两条对角线(弦)交于一点，因此每4点组成的集合对应于一个交点．由于没有3条弦交于一点，所以不同的4个点对应于不同的交点．

反之，设点P是弦A1A3与A2A4的交点，则P是4点集{A1,A2,A3,A4}对应的点．所以，交点的个数就是这n个点中取4点的取法总数Cn．

(2)圆周上n个点可组成Cn条弦，由(1)知，这些弦在圆内有Cn个交点．现把这些弦一条一条地取消．如果一条弦在圆内与k条弦相交，那么k个交点把这弦分为是k?1段，每一段是两个区域的公共边界，在这条弦取消后，这两个相邻的区域就合二为一，所以区域的个数减少k?1．这样逐步减少弦，直至最后弦全部取消，而区域只剩下一个(即整个圆)．

将上述过程追溯回去，即一条接一条地添弦，每添一条弦，区域的个数相应地增加k?1，这里k是所添的弦与已有弦在圆内的交点．所有的k的和是Cn，而弦有Cn条，所以区域总数是1?Cn?Cn．

3.解：设这n条直线的交点所成的集为P，则至少有n?2条直线，它的两侧都有P中的点．

事实上，如果上述命题不对，则至少有3条直线，使得P中的点均位于它们的同一侧，设这3条直线构成的三角形为ABC．因为第4条已知直线不能与?ABC的3条边均相交，所以它至少与?ABC一条边的延长线相交，不妨设它与AB边的延长线交于一点D，那么点A，D就位于直线BC的两侧，矛盾．

在这n条直线中任取一条l，则有

（1）如果P中的点全在l的同一侧（至多两条），选取P中与l距离最近的点A，A是另外两条直线l1，l2的交点，则由直线l，l1，l2围成的三角形与其他已知直线均不相交（否则，

P中将有一个比点A距l更近的点），因此，这样的直线至少对应着一个三角形．

（2）如果P中的点在l的两侧（至少n?2条），用上述方法可产生两个三角形，因此这

42必非负．但是，这个5×7棋盘中，有12个小方格中是“?2”，23个小方格中是“?1”，即

35个方格诸数之和为?2?12?23??1，因而k层特利米诺角片盖住的小方格中诸数之和为?k，矛盾．

例8．设Oxyz是空间直角坐标系，S是空间中的一个有限点集，Sx，Sy，Sz是S中所有点分别在坐标平面Oyz，Ozx，Oxy上正投影所成集合，求证：|S|2?|Sx|?|sy|?|Sz|．

?i,j,z)?S}证明：对任意(i,j,0)?Sz，令Tij?{(i,j,z)|(显然s?(i,j,0?Tij，由柯西)sz42442（Cauchy）不等式得

2|S|??1?(i,j,0)?sz2?(i,j,0)?Sz|Tij|?|Sz|?2?(i,j,0)?Sz|Tij|．① 考虑集合V?2?(i,j,0)?Sz2(Tij?Tij)，

这里Tij?Tij?{((i,j,t1),(i,j,t2))|(i,j,tk)?S,k?1,2}，显然|V|??(i,j,0)?sz|Tij|．定义映射

f:V?Sx?Sy为：V?((i,j,t1))，(i,j,t2)?((0,j,t1),(i,0,t2))?Sx?Sy，

不难看出f为单射，因此有|V|?|Sx?Sy|?|Sx||Sy|． 由①及②得|S|?|Sx|?|Sy|?|Sz|．

②

习题参考：

1.解：以S中的每一点为中心作圆，使这个圆上至少有S中的k个点．这样就得到了n个圆C1，C2，?，Cn．设点Pi(1?i?n)出现在ai个圆上，如果一个点同时在若干个圆上，我们就重复计算若干次．考虑任意两个圆Ci，Cj，每两个圆至多有2个交点，因此，至多有

2C个交点．因为m个圆交于某点时，这个交点就被计算了C次，因此，Pi被计算了C次，

2n2m2ai样的直线对应着2个三角形．

由于每个三角形对应着3条直线，所以三角形的个数不少于

4.下面我们用数学归纳法证明：对平面上已给的n(?2)个点，按题设方式染色，至少有

2(n?2)?23?23(n?1)．

（讲座四）5

2n?3个红点．

奠基是显然的．

?A1A3A4之一中，由(1)的讨论知，M具备(II)．

假设命题对n?1成立．考虑n个点的凸包，设它是凸m边形A1A2?Am．去掉顶点A1后，剩下的n?1点利用归纳假设，至少有2(n?1)?3?2n?5个红点．

设B，C分别是A1A2，A1Am上距A1最近的已知点，如图所示，则A1B，A1C的中点显然不在上述2n?5个红点之内，故n个点时至少有2n?5?2?2n?3个红点． 当凸包为一条线段A1An时，设A2为距A1最近的已知点，A3为距A1次近的已知点，则A1A2，A1A3的中点不与其他红点相同，这时也至少有2n?5?2?2n?3个红点．

综上可知，命题对一切自然数n(?2)都成立．特别地，当

n?998时，红点个数至少有2?998?3?1993个

另个，存在恰有1993个红点的特例．

在数轴上取998个点，它们的坐标是0,2,4,6，?，1994．于是坐标为1，2，3，4，5，?，

(3)M的凸包是五边形A1A2A3A4A5，则A6必在?A1A2A3，?A1A3A4，?A1A4A5之一的内部，由(1)知，M具备(II)．

(4)M的凸包是六边形A1A2A3A4A5A6，因6个内角和为(6?2)?180??720?，所以必有一个内角?

6.解：首先考虑边不平行BC的小菱形，延长每个菱形的边顺次与BC相交于4个分点（特殊情形下，第2个交点与第3个交点重合于菱形的一个顶点）为了便于处理，可延长AB到B?使BB??1nAB，延长AC到C?使CC??1nAC，并延长各平行线交线段B?C?于n?2个等

720?6． ?120?，设么?A1A2A3?120?，则M具备（II）

总之，集M必具备(I)，（II）两种情形之一，从而命题成立．

1992，1993的点就是全体整点，恰好1993个．

5.设这6点集为M?|A1,A2,A3,A4,A5,A6|．于是有

（1）若M中有三点共线．设A1，A2，A3依次一直线上，并且A1A2?A2A3，于是?6?A1A3A1A2?2?3．

分点，记为0，1，2，?，n?1 (包括B?，C?两个端点)，于是每边不平行BC的小菱形的两组对边延长后交B?C?于4个不同分点i，i?1，k，k?1．反之，任给这样4个分点必对应一个边不平行BC的小菱形，二者且有一一对应关系．由于有序数组(i,i?1,k,k?1)(0?i?i?1?k?k?1?n?1)又与有序数组（i?1,k）（1?i?1?k?n）一一对应，故边不平行于BC的小菱形的个数为Cn．由对称性，所求小菱形的个数3Cn．

22（2）若M中有3个点所构成的三角形的一个内角不小于120?，不妨设在?A1A2A3中，

?A1A2A3?120?，并设A1A2?A2A3，于是，由余弦定理，

A1A3?A1A2?A2A3?2A1A2?A2A3cos?A1A2A3222

?A1A2?A2A3?2A1A2?A2A3cos120?

?A1A2?A2A3?A1A2?A2A3?3A1A2，所以?6?22222A1A3A1A2?3．

因此，若M中的点具有（I）或（II），则命题得证．

现在考虑M的凸包，且设M不具备(I)，下证M必具备(II)．

(1)M的凸包是三角形，设为?A1A2A3，则?A1A4A2，?A2A4A3，?A3A4A1中至少有一个不小于120? (因它们的和为360?)，于是?A1A4A2，?A2A4A3，?A3A4A1中至少有一个具备(II)．

(2)M的凸包是四边形，设为A1A2A3A4．连接对角线A1A3，则A5必位于?A1A2A3与

（讲座四）6

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第4讲 组合几何 长沙市一中 申东在线全文阅读。