组合几何嵌入问题的研究-

1、组合几何嵌入问题的研究数学学院 数学与应用数学（师范）专业 2010级 指导教师 摘 要：现今的高考考题注重考查学生的逻辑思维能力、运用能力、分析问题和解决问题的能力，而嵌入问题的求解能很好的锻炼学生这方面的能力。组合几何正式成为一门数学分支只有半个世纪历史，但是与组合几何有关的问题，却可追溯到遥远的历史深处，比如中国的七巧板、波斯的织毯等。组合几何绝对称得上最困难、最有趣、联系最广泛的。本文将主要研究嵌入问题的方法，帮助学生提高各方面能力。关键词：嵌入；覆盖；图形结合；解题方法 Abstract: Nowadays, the college entrance examination focu

2、s on testing students ability of logical thinking, analyzing and solving problems. And these abilities can be improved by solving the embedding problems. Althrough the history of the combinatorial geometry became a branch of mathematics is only half a century, problems related to the combination of

3、geometry can be traced back to thousands of years ago, such as the Chinses Tangram and the Persian carpet. The combination of geometric is absolutely the most difficult, the most interesting, and most widely contact in mathematics. This article will mainly study the method of embedding, aim to help

4、student improve their relevant abilities. Key words: Embedded; Cover; Graphics; The method of solving problems.1 引言组合几何是组合学与几何学的孩子，它既秉承了组合学灵活的特性，又具有美丽的几何外形。虽然组合学与几何学都已有数千年的历史，但组合几何这个名字在上世纪中叶才被数学家H.Hadwiger首次使用。1964年H.Hadwinger等人合著的平面组合几何是标志组合几何学诞生的第一本专著。组合几何中充满了问题，有老问题也有新问题。有部分解决的，也有完全未解决的。其中包括形形色色的

5、嵌入与覆盖问题，比如求n个单位正方形能嵌入的最大正方形的边长问题；用带形去覆盖凸形及环形的问题；求能够嵌入单位正方形的n个正方形的边长和的最大值问题.它们都是组合几何中的主要研究内容，具有非常重要的理论意义和实际意义。嵌入与覆盖关系密切。一个集合M覆盖另一个集合N，也就是集合N能嵌入集合M。求能嵌入正方形的最大正三角形等同于求覆盖正三角形的最小正三角形。嵌入与覆盖往往互为对偶。用多少单位圆可以覆盖一个正方形，它的对偶问题就是一个正方形内可以嵌入多少个圆。用一系列正方形去覆盖一个正方形的对偶问题是将一系列正方形嵌入一个正方形。我们首先给出嵌入与覆盖的一般定义。对于d-维欧几里德空中的凸体列，,.

6、凸体，若存在刚体运动使得(=1,2)两两内部不交，且（=1，2，)为的子集，则称凸体列，可嵌入凸体。若存在刚体运动使得（=1，2，），则称凸体列，可覆盖凸体。本文仅讨论二维平面中的一类嵌入与覆盖问题。2 嵌入定义2.1 设为一正方形列。其中，的边长为，则称为正方形列的最小潜入函数。由嵌入的定义，易得下面定理：定理 2.1 .下给出的一个上界：定理 2.2 1+.为证明以上定理，需给出如下已知结果：引理2.32 边长分别为，总面积为的正方形列当满足，并且 . （1）时，可以嵌入边长为的矩形内。为了完整起见，我们在此列出它的证明： 证明 如图2-1所示，将正方形依大小顺序一个接一个地放入的矩形中。

7、先排第一行，边长为的旁边紧接着边长为的，这样排下去，直至无法再排。然后在的矩形中再排第二行。依次类推，设第排的第一个正方形边长为，则，并且对， . (2) 图2-1将行的正方形的面积之和 , （3）求和得 , （4）将（1）代入（4）并化简得 . （5）（5） 表明一行接一行地排小正方形，各行高的和不会超过，所以这些小正方形可以逐一嵌入的矩形中（参见图2-1）。 证明 令，则有。对任意，有。在引理2.3中，取，易得出正方形列，都能嵌入边长为的正方形内。由的任意性及的最小性，有。 定理2.48 当时，。其中，为方程0的一个根。 证明 由嵌入的定义，边长分别为1和的正方形与内部交为空，若将与嵌入任

8、意边长的正方形，显然必有，因此+ 图2-2 另一方面，将与如图2-2所示放置，当（为方程的一个根）时，由引理2.3，都能嵌入边长为的长方形中。从而，都能嵌入边长为的正方形。由嵌入函数的定义，。故有=。 定理2.58 当时，正方形列能嵌入边长为的正方形中，其中为方程的一个根，为方程的一个根。 证明 当时，。设为一边长等于的正方形。首先，由的取值，显然能将如图2-3所示放置在中。 图2-3因为 = = 故可如图2-3放在上方。又有 = =。因为所以。故 。从而可如图2-3所示，紧挨着放在左侧（其低与的低在同一高度）。当时，可验证和同时成立。故可如图2-3所示放置在,所夹的长方形中。而此时也有成立，

9、因此可如图2-3所示并排在的右侧。在的取值条件下，又有和=同时成立，故可嵌入的长方形中，从而可嵌入边长为的正方形中。 例2.6 证明在任一面积为的凸形里都可以嵌入一个三角形，它的面积;。 （1） （2） 图2-4 证明 如图（1），先作两条平行的支持直线，、分别为它们与凸形的公共点。弦将凸形分成两部分，有一部分的面积。 再作与平行的支持直线，它与凸形的较大部分有公共点。及三条支持直线构成平行四边形，其面积。的面积是平行四边形的一半，因而面积大于或等于。 设是凸形的内接三角形中面积最大的。、分别为、的中点。 过、分别作对边的平行线，构成（如图（2）。凸形没有点在外，否则设有一点在异侧，则的面积大

10、于的面积，矛盾！ 显然。这就给出的另一个证明（、实际上是凸形的支持直线），但要证明，还需要稍细致的分析。 将凸形在内的部分关于作中心对称得到完全在内的“弓形”。类似地得出弓形、。如果这三个弓形没有公共内点，那么三个弓形面积之和，从而。 下面证明这三个弓形的确没有公共内点。 假设是这三个弓形的公共内点。作关于、的对称点、，则，。所以。 由于是三个弓形的公共内点，所以、在凸形内。并且有一个以为心的小圆在弓形内，从而也有一个以为心的小圆在凸形内（两个小圆关于对称）。这就表明在延长线上还有一点在凸形内。凸形的内接三角形的面积，因而也就大于的面积，与的最大性矛盾。 优于，但这不是最好的结果。用稍高级的工

11、具，1917年W.Blaschkg证明了凸形内的面积最大的三角形，面积，为凸形的面积。并且等号当且仅当凸形为椭圆时成立。 例2.7 证明单位正方形内任意四点中必有两点的距离。 图2-5 证明 我们证明更强一点的结论：半径为的圆内任意四点中必有两点的距离。 设为其中两点，且，又设半径分别过。的“直径”（即中每两点的距离的最大值）是它的最大边，由于,所以是直径，并且。 因此，可以假定四个点都在圆周上（必要时用代替,两点间的距离不会减少）。 如果每两个点距离大于等于1，那么每相邻两点之间的（劣）弧不小于四分之一圆周，从而相邻两点间的弧恰等于四分之一圆周，每两点之间的距离的最小值恰等于1。 对于圆来说

12、，下面的四个问题等价： 个相等的圆能嵌入单位圆中，圆半径的最大值是多少？ 个单位圆能嵌入一个圆中，这圆的半径至少多大？ 在单位圆中取个点，每对点之间的距离的最小值至多多大？ 在一个圆中有个点，每两点之间距离，这圆的半径至少多大？ 采用第三个问题的说法，记所说最小值的最大值为。在时，并且在个点构成圆内接正边形时达到最大值。在时，在个点中一点为圆心，其余点成圆内接正边形时达到最大值。U.Pirl在1969年证明了 嵌入的点集，除讨论其两点间距离最小值的最大值外，还可以对其它有关的量进行研究。3 覆盖例3.1 有限多个单位圆所覆盖的面积为,证明可以从中选出若干个互不重叠的圆，总面积不小于。 图3-1

13、证明 考虑平面上的格点，这些格点组成边长为4、一个角为的平行四边形（图3-1）。每个平行四边形的面积为。 所述单位圆覆盖的区域分布在若干个平行四边形内，将这些平行四边形剪下叠到一个平行四边形上。设（表示不小于的最小整数，如），则中至少有一点被覆盖了次。这一点及移过来与它重叠的点，原先两两间的距离都是平行四边形的边长4的整数倍。取含这个点的个单位圆。这些圆互不重叠，而且总面积。例3.2 已知5个同样大小的正方形可以覆盖正方形，证明4个这样的正方形就可以覆盖正方形。 （1） （2）图3-2证明 设正方形的中心为，各边中点为、。只需证明5个小正方形的边长（不妨设）。假设小正方形的边长小于。每个小正方

14、形至多盖住、中的一个点（因为每两个点的距离小正方形的直径），因而每个小正方形恰好盖住这五点中的一个点。图5.2表明图5.1中的点各属于哪一个正方形（1表明属于1个正方形等等）。设第1个正方形在正方形的周界上覆盖的部分为、（图5.1），则 ，所以 .即正方形1覆盖的部分不足正方形的周界的。于是4个小正方形1、2、3、4不能完全覆盖正方形的周界，从而周界上必有点属于正方形1或4。不妨设属于正方形1.这时不属于正方形1.只能属于正方形2或5.但的面积为 ，而正方形5的内接三角形的面积,所以不属于正方形5。同理不属于正方形5。属于正方形2。若属于正方形3，则上的点均不属于正方形3，否则这点与、构成面积

15、为的内接三角形。于是正方形完全被正方形2与5覆盖。但“一个正方形不能被两个较小的正方形覆盖”（注）。矛盾表明不属于正方形3，因而属于正方形4. 与前面推理相同，上没有属于4的点。正方形2至多盖住上长为的一段，正方形5与此类似。所以正方形1至少盖住、上总长.但一个正方形的周界不能被较小的正方形盖住一半或一半以上，矛盾！因此5个小正方形的边长。例3.3 若的三边的平方和，则可以用一个单位圆覆盖。证明 设，则由于 ，所以。若，则过作单位圆，弧所对圆周角不超过，而，所以在圆内。设。由中线公式 ，所以。于是以中点D为心的单位圆覆盖。例3.4 已知5个同样大小的正三角形可以覆盖正三角形，证明4个这样的正三

16、角形就可以覆盖三角形。证明 三角形的三个顶点及三边的中点共6个点。5个小的正三角形能覆盖住这6点，因而其中必有一个至少盖住2个点。所以小三角形的直径大于等于。这里的直径指小三角形内任意两点的距离的最大值，也就是这三角形的最大边。于是小正三角形的边长至少是的边长的一半，4个这样的三角形显然能覆盖。4 结束语结合前面的这些例子我们可以看出嵌入与覆盖问题在组合几何中占有相当重要的地位，因此研究嵌入与覆盖问题成为学习组合几何中必经的一个过程。本文介绍的嵌入与覆盖的定理及其求法，我们可以利用这些数学思想解决更多的数学问题。更有利于提高我们的逻辑思维能力、运用能力、分析问题和解决问题的能力。参考文献：1

17、H.L.Abbott,M.Kachalski,Covering squares with squares,Discrete and computational geometry,Vol.24(2000),151-169.2 J.Pack and P.K.Agarwal, Combinatorial Geometry, Wiley, 1995.3 J.W.Moon and L.Moser, Some packing and covering problems. Colloq.Math.17(1967), 103-110.4 W.Moster and J.pach,Recent developme

18、nt in combinatorial Geometry,in New Trends in Discrete and Computational Geometry,Algorithms and Combinatorics,Vol.10,Spring-Verlag,Berlin,1993,pp.281-302.5 P.J.Federico,Squaring rectangles and squares in Graph Theory and Re-lated Topics J.A.Bondy and U.S.R. Murty,eds, Academic Press,New York,1979,PP.173-196.