第77讲组合几何(新)

第16讲组合几何本节主要内容是组合几何，几何中一些组合性质的问题．按照数学家厄迪斯的说法，凸性、覆盖、嵌入、计数、几何不等式、等都属于这类问题．凸包和覆盖、几何不等式问题分别在第6讲、第15讲已经着重讲解过，本讲仍有所涉及，本讲涉及组合计数、几何极值、几何图形的分割和一些组合几何杂题．A类例题例1证明：任何面积等于1的凸四边形的周长及两条对角线之和不小于4+22.(1985年奥地利和波兰联合数学竞赛试题)分析先考虑两种特殊情形：面积等于1的正方形和菱形.在正方形中周长为4,对角线之和为22；在菱形中,两条对角线长分别为l1和l2,则因面积面积S=12l1l2=1,故l1＋l2≥2l1l2=22,而周长=4(l12)2+(l22)2=2l12+l22≥22l1l2=4.故两种特殊情形之下结论成立．这就启发我们可将周长和对角线分开来考虑．证明设ABCD是任一面积为1的凸四边形(如图)，于是有1=12(eg+gf+fh+he)sinα≤12(eg+gf+fh+he)＝12(e＋f)(g+h)≤12(e＋f+g+h2)2,即对角线之和为e＋f+g+h≥22．再按图的方式最新将图形中线段和角标上字母，于是又有2=2S四边形ABCD=12absinβ1+12bcsinβ2+12cdsinβ3+12dasinβ4≤12(ab+bc+cd+da)=12(a+c)(b+d)≤12(a+b+c+d2)2,则a+b+c+d≥4.综上所述,命题结论成立．说明几何不等式的证明通常引进几何变量后化归为代数不等式的证明，其中均值不等式和柯西不等式经常使用．例2在平面上给定五个点，连接这些点的直线互不平行、互不垂直，也互不重合．过每一点作两两连接其余四点的所有直线的垂线．若不计原来给定的五点,这些垂线彼此间的交点最多能有多少个？(第6届IMO试题)分析先考虑所有五个点间的连线的情况，再考虑每点向所有连线作的垂线的情况，利用多个点向一条直线作垂线没有交点，三角形的三条高线交于一点，将多计数的交点一一剔除．解由题设条件，给定的五个点之间的连线共有C52=10条,这些点构成的三角形共有C53=10个．过给定五点中的每一个作不通过该点连线的垂线共有5C42=30条．若此30条垂线两两互不平行,它们的交点也互不重合,则共有C302=435个交点．然而，在本问题中的30条垂线有相互平行的,也有交点重合的,故应从435个交点中减去多计入的交点个数．首先，对于任一条连线，过其余三点所作该连线的三条垂线是彼此平行而无交点的，故应从总数中减去由此多计入的10C32=30个交点；其次，对于由这些连线构成的每一个三角形来说，三条高同交于一点，而这三条高也为所作的垂线，故应从总数中再减去10(C321)=20个多计入的交点；又过每一顶点所作其余连线的垂线都重交于该顶点，而欲求交点数是不记入该五个顶点的，故又应从总数中再减去5C62=75个多计入的顶点(恰有C42=6条垂线在一顶点处相交)．故至多有435203075=310个交点．说明简单的组合计数问题和普通的排列组合问题解决的方法类似，必须做到既不遗漏，也不重复(不多算，也不少算)，复杂的问题还要构造递推关系、利用映射、算两次、数学归纳法等思想方法加以考虑，见本书其它讲座．情景再现hgfeDCBA4321dcbaBADC1.在平面上给定正方形ABCD,试求比值OA+OCOB+OD的最小值，其中O是平面上的任意点．(1993年圣彼得堡市数学选拔考试试题)2.由9条水平线与9条竖直线组成的8×8的棋盘共形成r个矩形，其中s个正方形，sr的值可由mn形式表示，其中m,n均为正整数，且mn是既约分数.求m+n的值.(1997年美国数学邀请赛试题)B类例题例3已知边长为4的正三角形ABC，D、E、F分别是BC、CA、AB上的点，且|AE|=|BF|=|CD|=1，连接AD、BE、CF，交成△RQS，P点在△RQS内及其边上移动，P点到△ABC三边的距离分别记作x、y、z.1.求证：当P点在△RQS的顶点时，乘积xyz有极小值；2.求上述乘积的极小值.（1982年全国高中数学联赛试题）分析逐步调整法先固定x，考虑yz的最小值.然后又由对称性扩大P点的变化范围求乘积xyz的极小值．解1.如图，第一步，先固定x，考虑yz的最小值.即过P作直线l∥BC，当P在l上变化时，yz何时最小.第二步，先证两个引理：引理1：x+y+z=定值，这个定值就是正三角形的高.引理2：设y∈[α,β]，y的二次函数y(a—y)在[α,β]的一个端点处取得最小值.引理1的证明用面积法，引理2的证明可用配方法.（证明留给读者）由两个引理不难得到：如果P’,P’’为l上的两点，那么当P在区间[P’,P’’]上变动时，xyz在端点P’P’’处取得最小值.第三步，扩大P点的变化范围：根据上面所述，当P点在l上变动时，xyz在端点P’或P”处为最小，这里P’、P”是l与△RQS的边界的交点，但△RQS的边不与△ABC的边平行，因而在P移到△RQS的边界后，不能搬用上述方法再将P’或P”调整为△ABC的顶点.但是我们可以把P’点变化区域由△PQR扩大为图中所示的六边形RR’QQ’SS’,其中RR’∥Q’S∥CA,R’Q∥S’S∥BC,Q’Q∥RS’∥AB,也就是说:R与R’关于∠ABC的平分线为对称.S’与R关于∠ACB的平分线为对称,等等.过P作平行于BC的直线l,将P调整为l与六边形RR’QQ’SS’的边界的交点P’(或P”),再将P’调整为顶点R或S’,每一次调整都使xyz的值减小.由于对称,xyz在六个顶点R,R’,Q,Q’,S,S’处的值显然相等,因而命题成立.2.由题易知，△ABE≌△BCF≌△CAD，从而△AER≌△BFQ≌△CDS，△RQS是正三角形.由1，我们只考虑S点x，y，z的取值.由于△ASE∽△ADC,故|AS|:|SE|=4:1,由于△AFQ∽△ABD,故|AQ|:|QF|=4:3.所以故|AS|:|SQ|:|QD|=4:8:1,又由于△ABC的高h=12,故可求得3193,,,1313131936483(12).1313132197xhyhzhxyz====鬃?说明本题用到二次函数的基本性质：定区间上二次函数的最值只能在端点或对称轴处取到．例4设一凸四边形ABCD，它的内角中仅有∠D是钝角，用一些直线段将该凸四边形分割成n个钝角三角形，但除去A、B、C、D外，在该凸四边形的周界上，不含分割出的钝角三角形的顶点，试证n应该满足的充要条件是n≥4.(1993年全国高中数学联赛第二试试题)分析充分性：采用构造法.先连AC，再以AC为直径作半圆，由直径所对的圆周角是直角启发构造4个钝角三角形.必要性：先证非钝角三角形不能分成两个钝角三角形.再证n≥4.解充分性P''P'SQRCPBAR'S'Q'EDF(1)非钝角三角形一定可以分割成三个钝角三角形.事实上，取锐角三角形任一顶点，或直角三角形直角顶点，设为B，向对边AC作高BG，再以AC为直径向三角形内作半圆，于是，BG把位于该半圆内的任意点E与三顶点连线将三角形分割成三个钝角三角形△ABE、△BCE、△CAE，即为所求.(2)凸四边形ABCD可分割成4个钝角三角形.如图，连线段AC，又由(1),△ABC可分割成三个钝角三角形，加上钝角△ACD，共有4个钝角三角形.(3)凸四边形ABCD可分割为n=5，6，…个钝角三角形，如图，作AE1、AE2、…，即得新的分割的钝角三角形△AEE1，△AE1E2，…共有5，6，…个钝角三角形(外角∠AE1C＞∠AEC＞900,∠AE2C＞∠AEC,…)必要性先指出一个事实：非钝角三角形不能分割成两个钝角三角形.这是因为由任一顶点向对边作分割线段与对边的夹角不能将180o分成两个钝角，所以不能分割成两个钝角三角形.设凸四边形已被分割为n个钝角三角形，如果该凸四边形的四条边分别属于4个不同的钝角三角形，则已证得了n≥4.如果有两条邻边同属于一个钝角三角形(不相邻的两边不能构成三角形)，这时有下列两种情况之一发生：(I)该两邻边夹角为钝角∠D，于是∠D不能分割.这时AC必为分割线.非钝角三角形△ABC必被再分割之，它不能分割成2个钝角三角形，只能分割成3个以上的钝角三角形，连同钝角三角形△ADC，有n≥4.(II)该两邻边的夹角不是∠D，这时夹角不能是∠B，因为△ABC不是钝角三角形，因为夹角只能是∠A或∠C而使BD为分割线，并且将∠D分割出一个钝角，使该两邻边构成钝角三角形的两条边，这样，另一非钝角三角形必被再分割之，于是同理必须分割成3个以上的钝角三角形，同理得到n≥4.说明组合几何在全国高中数学联赛加试中经常出现，本题的难点在必要性的证明，充分性的证明只要构造就好了．例5设凸四边形ABCD的面积为1，求证在它的边上(包括顶点)或内部可以找到四个点，使得以其中任意三点为顶点所构成的四个三角形的面积均大于14.(1991年全国高中数学联赛第二试试题)分析在四个三角形△ABC、△BCD、△CDA、△DAB中选出一个面积最小的，然后按其面积与14的大小分四类情况加以讨论.证明如图(1)，考虑四个三角形△ABC、△BCD、△CDA、△DAB的面积，不妨设S△DAB为最小.这时有四种情况：(1)S△DAB14.这时显然A、B、C、D即为所求的四个点.(2)S△DAB14.设G为△BCD的重心.因S△BCD=1－S△DAB34,故S△GBC=S△GCD=S△GDB=31S△BCD14.于是，B、C、D、G四点即为所求.(3)S△DAB=14，而其它三个三角形的面积均大于14，由于S△ABC=1－S△CDA43=S△BCD,故过A作BC的平行线l必与线段CD相交于CD内部的一点E.由于S△ABCS△DAB,故S△EABS△DAB=14.又S△EAC=S△EAB,S△EBC=S△ABC14.故E、A、B、C四点即为所求.(4)S△DAB=14，而其它三个三角形中还有一个面积为14，不妨设S△CDA=14(如图(2))，因S△DAB=S△CDA，故AD∥BC，又S△ABC=S△DBC=34.故得BC=3AD.在AB上取点E，DC上取点F，使得AE=14AB，DF=14CD，那么，EF=41(3AD+BC)=23AD,BCADGEE1E2OBCADGBCADEEFS△EBF=S△ECF=43S△ABF=43×21S△ABC14,S△EBC=S△FBCS△EBF41.故E、B、C、F四点即为所求.说明分类的方法可以与证法一不同.(4)的证明可按下面的方法处理S△DAB=14，而其它三个三角形中还有一个面积为14，不妨设S△CDA=14(如图)，因S△DAB=S△CDA，故AD∥BC，过AC、BD的交点O作EF∥BC,分别交AB、CD于E、F，则EF=2·34AD=32AD.S△EBF=S△ECF=32×34S△DAB＞14,S△EBC=S△FBC＞S△EBF＞14.故E、B、C、F四点即为所求.情景再现3．设AB,CD是以O为圆心，r为半径的两条互相垂直的弦．圆盘被它们分成的四个部分依顺时针顺序记为X,Y,Z,W．求A(X)+A(Z)A(Y)+A(W)的最大值与最小值，其中A(U)表示U的面积．(1988年IMO预选题)4．设整数n(n≥5).求最大整数k，使得存在一个凸n边形(凸或凹，只要边界不能自相交)有k个内角是直角．(第44届IMO预选题)5.设ABCD是一个梯形(AB∥CD),E是线段AB上一点,F是CD上一点,线段CE与BF相交于点H,线段ED与AF相交于点G..求证:SEHFG≤14SABCD.如果ABCD是一个任意凸四边形,同样结论是否成立?请说明理由.(1994年中国数学奥林匹克试题)C类例题例6在平面内任给n(n＞4)个点，其中任意3点不共线.试证：至少有Cn23个以上述所给定点为顶点的凸四边形.(第11届IMO试题)分析由于平面上任何5点(其中任意3点不共线)中必有4点是一个凸四边形的4个顶点，于是通过算两次的方法，利用排