组合几何（二）凸包与图形重叠问题.doc

高中数学竞赛讲座二试内容30组合几何（二）凸包与图形重叠问题一概念及方法1凸集：如果对于点集M中的任意两点A、B，线段AB上每一点都属于点集M，那么M就称为凸集（圆是凸集） 结论：任意多个凸集的交仍是凸集2凸多边形定义一：如果以多边形的顶点为端点的任何线段，完全包含于这个多边形中，则称此多边形为凸多边形定义二：如果多边形位于它任意一条边（延长线）的同侧，这样的多边形叫做凸多边形3凸包：给定平面上个点，一定存在一个凸边形或一条线段，完全包含点并且凸边形的个顶点（或线段的两个端点）是点集的一个子集这样的凸边形（或一条线段）便称为点集的凸包，它由给定的点集唯一确定4与有限点集有关的角度、线段长、面积等问题，经常需要借组凸包讨论点集的几何结构 二例题精选1平面上任意给定5个点，其中任三点不共线，则可选出四个点，这四个点能构成一个凸四边形的顶点Key：按凸包是五边形、四边形、三角形分类讨论2平面上有个点，其中任意四点都是凸四边形的顶点，证明：已知点是一个凸边形的顶点Key：考虑这n个点的凸包是一个凸k边形，过凸k边形的任一顶点引对角线，则必有一个点落在三角形的边界或内部，矛盾3设、是平面上的两个有限点集，无公共元素，并且中任意三点不共线，如果、中至少有一个点集至少包含五个点，证明：存在一个三角形，它的顶点都在中或都在中，而且内部不包含另一个集合中的点（26IMO预选题）Key: 在A中任取5个点，使得这5个点的凸包中不含A的其它点 （1） （2） （3）4平面上给定4n+1个点，任意三点不共线，证明：可以用其中的4n个点组成2n对，连接每对点的2n条线段至少有n个不同的交点ABCDE取BCDE四点ABCDE取ADEC四点Key: 利用数学归纳法，当n=1时，五个点A、B、C、D、E的凸包分凸五边形、四边形、三角形，假设当n=4k+1 时命题成立，那么由于平面内有限点的连线是有限多条，因此，存在一条直线L，它与给定点中任意两点的连线均不平行，将L平行移动，最初给定点在L的同一侧，经过平行移动可以使L的另一侧给定点的个数由0逐渐增加至5，我们开始时就选取这5个点，这5个点中两对点所成的两条线段的交点为M，剩下的1个点与其余4(n-1)个点，根据归纳假设它们可产生n-1个不同交点这n-1个交点与M位于直线L的两侧，从而得到n个不同的交点得证5在平面上给定六个点，其中任何三点都不在一直线上证明：在这六个给定的点中，可以挑出这样三个点，使得在这三个点构成的三角形中，有一个角不小于（匈牙利）Key :考虑这六个点的凸包，它是一个凸多边形，顶点是这些已知点的全体或一部分若凸包是六边形，那么必有一个内角如果凸包是三角形，那么有一已知点在这三角形内，则必有一个不小于，结论成立如果凸包是四边形或五边形，用对角线将它们剖分为三角形，必有一个三角形中有已知点这属于上一种情形，结论也成立6平面上有五个点，如果存在实数满足下列条件：（1）中任意三点不在同一条直线上；（2）对于每个三元组的面积都等于则中至少有两个相等Key：这5个点凸包有三种可能情形（1）凸包是五边形顶点为，于是和都是凸四边形，对于四边形，则有（2）凸包是四边形，其顶点依次为，不妨设在内，于是和都是凸四边形，同（1）得；（3）凸包是，另两点在该三角形内，于是7平面上任给五个相异的点，它们之间的最大距离与最小距离之比记为，求证：（1985年全国）Key: 若凸包是凸五边形ABCDE，至少有一个内角不小于，不妨设，由正弦定理得若凸包为三角形或四边形，存在一个一个内角不小于120度的三角形，可得若凸包是线段，此时有8给定平面上个点（），无三点共线证明：在这各个点中可以挑出三个点，使得从其中一个点引出的通过其他两个点的射线之间的夹角不超过Key: 记给定的n个点为，（1）若组成凸n边形时，必有一个内角，过此顶点引出n-2条对角线，则确定一个角（2）考虑此图形的凸包是凸k边形，同样可以考虑，（1）可以省略9平面上给定五个点，其中无三点共线，试证每三点确定的三角形面积中，最大与最小的比不小于Key：（1）凸包是三角形及凸四边形时：不妨设在内部，有（）若凸包是凸五边形时，在对角线上取点、，使得：若同侧，不妨设为，则若同一侧，对角线必相交，设交点为，则10两个同样大小的正方形相交错，其公共部分构成一个八边形，一个正方形的边是蓝色的，另一个正方形的边是红色的，证明：八边形中蓝色的边长之和等于它的红色边长之和Key1：（1）两个正方形中心重合时，所构成的八边形外切于以中心为圆心、正方形边长为直径的圆，由切线长定理即得（2）中心不重合时，其中一个正方形可沿另一个正方形的两边平移使得中心重合，只需证明平移时红边长度之和不变Key2：图中的小三角形都相似，红边之和：红色高线之和=蓝边之和：蓝色高线之和，而红色三角形面积之和=蓝色三角形面积之和，由红色三角形与蓝色三角形有公共的底边八边形，则红色高线之和与蓝色高线之和相等，所以红边之和与蓝边之和11已知正方形和三角形都外切于半径为1的圆，证明：正方形和三角形的公共部分的面积必大于3.4，并问能否肯定这样的面积大于3.5？(1986俄罗斯)Key: 当外切三角形的边不平行于外切正方形的边时，三角形的边截正方形一角所成的直角三角形便在“公共部分”之外，先讨论这样的直角三角形面积如图二，作直角三角形使两边与正方形的两边成45度角，而第三边使得，这时公共面积S，只需证：，令三练习1在平面上给出不在同一直线上的四个点，证明：以这些点中任意三点为顶点的三角形中至少有一个不是锐角三角形key：分凸包是四边形与三角形讨论2平面上给定六个点，试证明任意两点距离之中最大与最小的比不小于3平面上任意给定5点，其中任三点不共线，则在以它们为顶点的三角形中，至多有7个锐角三角形4平面上给定n(n4)个点，每三个点不共线，证明：至少有个凸四边形以已知点为顶点三练习1在平面上给出不在同一直线上的四个点，证明：以这些点中任意三点为顶点的三角形中至少有一个不是锐角三角形2平面上给定六个点，试证明任意两点距离之中最大与最小的比不小于3平面上任意给定5点，其中任三点不共线，则在以它们为顶点的三角形中，至多有7个锐角三角形4平面上给定n(n4)个点，每三个点不共线，证明：至少有个凸四边形以已知点为顶点组合几何（三）图形覆盖问题一概念1覆盖是指两个点集，其中一个点集可以覆盖另一个点集，即：设M、N是两个点集，如果点集M中的每一个点都在点集N内，我们就说点集N覆盖点集M，否则称点集N不覆盖M2方法：覆盖问题要求我们在对基本图形比较熟悉的基础上，善于通过试验找出解题方法，要能在图形中看出图在膨胀或收缩二例题ABCOABCO1已知ABC，试找出覆盖ABC的最小圆ABCOKey: （1）钝角三角形 （2）直角三角形 （3）锐角三角形关键：覆盖圆的直径=2正方形内排列着n个互不相交且互不包含的圆，证明：可以把正方形划分成n个凸多边形，使得每个多边形内恰有一个圆（1991年国家集训队试题）Key：设这些圆为，定义点集，由于任两圆互不相交且互不包含，因此，每两个圆在它们的根轴的两侧，不与根轴相交易知覆盖了整个正方形，每一个围成的凸多边形与正方形的公共部分，因而是凸多边形，它包含圆3边长为2025的矩形内，任意放入120个边长为1的正方形，证明：在此矩形内总还可以再放入一个直径为1的圆，它与所有小正方形都不重叠（1961俄罗斯）Key: 要使直径为1的圆放入矩形，25200.5则其圆心应在除去边框（宽为0.5）的矩形内，其面积为2419=456，又若此圆不与任一单位正方形重叠，则其圆心应在每个正方形加上宽度为0.50.5的边框之外，正方形加框后的面积为由所以有一点不在加框的小正方形中，以此点为圆心，以0.5为半径所作的圆，在原矩形之内，且不与任一个小正方形重叠ABCDO3能否在半径为2的圆内，不重叠地放置8个边长为1的正方形（1990俄罗斯）Key: 证明ABCD的外接圆半径小于2DOBC4（1）设小圆的半径为r/2，大圆的半径为r，试问：最小要用多少个这样的小圆能将大圆盖住？（1974年匈牙利）Key：（2）在半径为R的圆上彼此不重叠地放半径均为r的小圆，当放有n个小圆时，大圆内不能再多放入一个半径为r的小圆，求证：Key：，将半径为r的小圆都换成半径为2r的同心大圆，这n个圆必完全覆盖住半径R-r的圆面（否则，若点P没被这n个圆覆盖住，则以P为圆心、r为半径的圆面与原来放的n个小圆不重叠，并且完全在半径为R内，矛盾），所以（方法说明：膨胀与缩小）5证明：任何一个周长为2a的多边形，总可以用一个直径为a的圆盖住（1956波兰奥林匹克）Key: 设W是周长为2a的多边形，在边界上取两个点A、B，使它们平分W的周长，则ABa以AB的中点O为圆心，a/2为半径作圆，对W上的任一点C， AC+CBa,延长CO到D，使OD=OC，则AD=CB，2OC=CD90度ACBD邻角A,B 90度21（ii） ABCD的凸包是凸四边形时，（I）对角A、C大于90度，以BD为直径；（II）邻角A、B小于90度，若2190度，以AB直径；若190度，作锐角三角形ABC的外接圆，D必在圆内8证明：单位长的任何曲线能被面积为0.25的闭矩形覆盖（1990年国家集训队）Key：如图，曲线端点连线记为L，设矩形ABCD是覆盖曲线的最小矩形且AB/CD/L，BDL，DAL，AB=a ,BD=b,则曲线和矩形四边都有公共点，在各边任选一个公共点，分别记为 ，又设曲线的端点是，则有ABCDPQ3549用正方形完全盖住边长分别为3cm、4cm、5cm的一个三角形，求这个正方形的最小边长（1986上海）Key：10在一个66棋盘上已经摆好了一些骨牌，每一张都覆盖两个相邻的格子。证明：如果至少还有14个格子没有被覆盖，则至少在放进一张骨牌，而不移动其它的骨牌（1984年匈牙利）Key：除第一行外，每个空格A对应于一张骨牌，这骨牌覆盖与A同列并在A上一行的方格如果对某个空格，这样的骨牌不存在，则棋盘上可以放进一个新骨牌，如果一张骨牌与两个空格对应，则这两个空格相邻的，因此可以放进一个新骨牌，所以可以假设上面定义的映射是一一对应的，因此在棋盘上端的56的矩形中的骨牌数与下端的56的矩形中的空格数相同显然我们可以假设第一行上的空格不多于3个，因此对应于11个空格，在上端的56矩形中至少有11张骨牌，因为棋盘上的骨牌不超过11张，所以，最下面一行全是空格，可以