tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

2012江苏省数学竞赛《提优教程》教案:第77讲


第 16 讲 组合几何
本节主要内容是组合几何,几何中一些组合性质的问题.按照数学家厄迪斯的说法,凸 性、覆盖、嵌入、计数、几何不等式、等都属于这类问题.凸包和覆盖、几何不等式问题分 别在第 6 讲、第 15 讲已经着重讲解过,本讲仍有所涉及,本讲涉及组合计数、几何极值、几 何图形的分割和一些组合几何杂题.

A 类例题
例 1 证明:任何

面积等于 1 的凸四边形的周长及两条对角线之和不小于 4+2 2.(1985 年奥地利和波兰联合数学竞赛试题) 分析 先考虑两种特殊情形:面积等于 1 的正方形和菱形. 在正方形中周长为 4,对角线之 和为 2 2; 在菱形中, 两条对角线长分别为 l1 和 l2, 则因面积面积 S= =2 2,而周长=4 1 l l =1,故 l1+l2≥2 l1l2 212

l1 l2 (2)2+(2)2=2 l12+l22≥2 2l1l2 =4. 故两种特殊情形之下结论成立. 这就启发

我们可将周长和对角线分开来考虑. 证明 设 ABCD 是任一面积为 1 的凸四边形(如图),于是有 1 1 1 1 e+f + g+h 2 1= (eg+gf+fh+he)sinα≤ (eg+gf+fh+he)= (e+f )( g+h) ≤ ( ), 2 2 2 2 2 即对角线之和为 e+f + g+h≥2 2. 再按图的方式最新将图形中线段和角标上字母, 于 是又有 2=2S 四边形 ABCD 1 1 1 1 = absinβ1+ bcsinβ2+ cdsinβ3+ dasinβ4 2 2 2 2 1 1 1 a+b+c+d 2 ≤ (ab+bc+cd+da)= (a+c)(b+d)≤ ( ), 2 2 2 2
B C D A e h A a D

?4

?1
b d

?
g f B

?2
c

?3
C

则 a+b+c+d≥4. 综上所述, 命题结论成立. 说明 几何不等式的证明通常引进几何变量后化归为代数不等式的证明,其中均值不等式 和柯西不等式经常使用. 例2 在平面上给定五个点,连接这些点的直线互不平行、互不垂直,也互不重合.过每 一点作两两连接其余四点的所有直线的垂线. 若不计原来给定的五点, 这些垂线彼此间的交点 最多能有多少个?(第 6 届 IMO 试题) 分析 先考虑所有五个点间的连线的情况,再考虑每点向所有连线作的垂线的情况,利 用多个点向一条直线作垂线没有交点,三角形的三条高线交于一点,将多计数的交点一一剔 除. 解 由题设条件,给定的五个点之间的连线共有 C2 5 =10 条, 这些点构成的三角形共有 3 C5=10 个.过给定五点中的每一个作不通过该点连线的垂线共有 5C2 4=30 条.若此 30 条垂线 2 两两互不平行, 它们的交点也互不重合, 则共有 C30=435 个交点.然而,在本问题中的 30 条 垂线有相互平行的, 也有交点重合的, 故应从 435 个交点中减去多计入的交点个数. 首先,对于任一条连线,过其余三点所作该连线的三条垂线是彼此平行而无交点的,故 应从总数中减去由此多计入的 10 C2 3=30 个交点;其次,对于由这些连线构成的每一个三角形来 说,三条高同交于一点,而这三条高也为所作的垂线,故应从总数中再减去 10(C2 3?1)=20 个多

计入的交点;又过每一顶点所作其余连线的垂线都重交于该顶点,而欲求交点数是不记入该五 2 个顶点的, 故又应从总数中再减去 5C2 6=75 个多计入的顶点(恰有 C4=6 条垂线在一顶点处相交). 故至多有 435?20?30?75=310 个交点. 说明 简单的组合计数问题和普通的排列组合问题解决的方法类似,必须做到既不遗漏, 也不重复(不多算,也不少算),复杂的问题还要构造递推关系、利用映射、算两次、数学归纳法 等思想方法加以考虑,见本书其它讲座.

情景再现
OA+OC 1. 在平面上给定正方形 ABCD, 试求比值OB+OD的最小值,其中 O 是平面上的任意 点.(1993 年圣彼得堡市数学选拔考试试题) s 2. 由 9 条水平线与 9 条竖直线组成的 8×8 的棋盘共形成 r 个矩形, 其中 s 个正方形, 的 r m m 值可由 形式表示,其中 m,n 均为正整数,且 是既约分数. 求 m+n 的值.(1997 年美国数学 n n 邀请赛试题)

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 有极小值; A 2. 求上述乘积的极小值.(1982 年全国高中数学联赛试题) 分析 逐步调整法 先固定 x,考虑 yz 的最小值. 然后又由对称性扩大 P 点的变化范围求乘积 xyz 的极小值. S S' 解 1.如图,第一步,先固定 x,考虑 yz 的最小值. 即过 P 作直线 l∥BC,当 P 在 l 上变化时,yz 何时最小. P' P 第二步,先证两个引理: F 引理 1:x+y+z=定值,这个定值就是正三角形的高. R 引理 2:设 y?[α,β],y 的二次函数 y(a—y)在[α, β] R' 的一个端点处取得最小值. B 引理 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 扩大为图中所示的六边形 R R’QQ’ S S’, 其中 R ’ R ∥Q’S∥CA, R’Q∥S’S∥BC, Q’Q∥RS’∥AB,也就是说: R 与 R’关于∠ABC 的平分线为对称. S’与 R 关于∠ACB 的平分线为对称,等等.过 P 作平行于 BC 的直线 l,将 P 调整为 l 与六边形 R R’QQ’ S S’的边界的交点 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.

E

P''

Q' Q

D

C

所以故|AS|:|SQ|:|QD|=4:8:1, 又由于△ABC 的高 h=

1 h, y = 13 1 9 xyz = 鬃 13 13 x=

12 ,故可求得 9 3 h, z = h, 13 13 3 648 3 ?( 12)3 . 13 2197

说明 本题用到二次函数的基本性质:定区间上二次函数的最值只能在端点或对称轴处 取到. 例 4 设一凸四边形 ABCD,它的内角中仅有∠D 是钝角,用一些直线段将该凸四边形分 割成 n 个钝角三角形,但除去 A、B、C、D 外,在该凸四边形的周界上,不含分割出的钝角 三角形的顶点,试证 n 应该满足的充要条件是 n≥4.(1993 年全国高中数学联赛第二试试题) 分析 充分性:采用构造法. 先连 AC,再以 AC 为直径作半圆,由直径所对的圆周角是 直角启发构造 4 个钝角三角形. 必要性:先证非钝角三角形不能分成两个钝角三角形.再证 n ≥4. 解 充分性 (1)非钝角三角形一定可以分割成三个钝角三角形. 事实上,取锐角三角形任一顶点,或直角三角形直角顶点,设为 B,向对 A 边 AC 作高 BG,再以 AC 为直径向三角形内作半圆,于是,BG 把位于该半圆 内的任意点 E 与三顶点连线将三角形分割成三个钝角三角形△ABE、△BCE、 G △CAE,即为所求. (2)凸四边形 ABCD 可分割成 4 个钝角三角形. 如图,连线段 AC,又由(1), △ABC 可分割成三个钝角三角形,加上钝角△ACD,共有 4 个钝角三角形. E (3)凸四边形 ABCD 可分割为 n=5,6,?个钝角三角形,如图,作 AE1、 E1 E2 AE2、?,即得新的分割的钝角三角形△AEE1,△AE1E2,?共有 5,6,?个 B 钝角三角形(外角∠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,求证在它的边上(包括顶点)或内部可以找到四个 1 点,使得以其中任意三点为顶点所构成的四个三角形的面积均大于4.(1991 年全国高中数学联 赛第二试试题) 分析 在四个三角形△ABC、△BCD、△CDA、△DAB 中选出一个面积最小的,然后按 1 其面积与 的大小分四类情况加以讨论. 4 D 证明 如图 (1), 考虑四个三角形△ABC、 △BCD、 △CDA、 A △DAB 的面积,不妨设 S△DA B 为最小.这时有四种情况:
A E E O G

D

C

D

F

B

C

B

C

1 (1)S△DA B> .这时显然 A、B、C、D 即为所求的四个点. 4 1 (2)S△DA B< .设 G 为△BCD 的重心. 4 3 因 S△BCD=1-S△DA B >4,故 1 1 S△GBC= S△GCD= S△GDB= S△BCD>4. 3 于是,B、C、D、G 四点即为所求. 1 1 3 (3)S△DA B=4,而其它三个三角形的面积均大于4,由于 S△A BC=1-S△CDA< =S△BCD, 4 故过 A 作 BC 的平行线 l 必与线段 CD 相交于 CD 内部的一点 E. 1 1 由于 S△A BC>S△DA B, 故 S△EA B>S△DA B=4.又 S△EAC=S△EA B,S△E BC=S△A BC>4.故 E、A、B、 C 四点即为所求. 1 1 1 (4)S△DA B=4,而其它三个三角形中还有一个面积为4,不妨设 S△CDA =4 (如图(2)), 3 因 S△DA B=S△CDA ,故 AD∥BC,又 S△A BC=S△D BC= .故得 BC=3AD. 4 1 1 在 AB 上取点 E,DC 上取点 F,使得 AE=4AB,DF=4CD,那么,

1 3 (3AD+BC)= AD, 4 2 1 3 3 1 S△EBF=S△ECF= S△A BF= × S△A BC>4, 4 4 2 1 S△E BC=S△F BC> S△EBF > . 4
EF=

A

D

故 E、B、C、F 四点即为所求. E 注 分类的方法可以与证法一不同. O (4)的证明可按下面的方法处理 1 1 S△DA B= ,而其它三个三角形中还有一个面积为 , 4 4 1 不妨设 S△CDA = 4(如图), B 因 S△DA B=S△CDA ,故 AD∥BC,过 AC、BD 的交点 O 作 EF∥BC,分别交 3 3 3 3 1 AB、 CD 于 E、 F, 则 EF=2? 4AD=2 AD. S△EBF= S△ECF=2×4 S△DAB>4, S△EBC= S△FBC>S△EBF 1 >4. 故 E、B、C、F 四点即为所求. 说明

F

C

情景再现
3.设 AB,CD 是以 O 为圆心,r 为半径的两条互相垂直的弦.圆盘被它们分成的四个部 A(X)+A(Z) 分依顺时针顺序记为 X,Y,Z,W .求 A(Y)+A(W)的最大值与最小值,其中 A(U) 表示 U 的面 积.(1988 年 I MO 预选题) 4.设整数 n(n≥5).求最大整数 k,使得存在一个凸 n 边形(凸或凹,只要边界不能自相交) 有 k 个内角是直角.(第 44 届 IMO 预选题) 5. 设 ABCD 是一个梯形(AB∥CD),E 是线段 AB 上一点,F 是 CD 上一点,线段 CE 与 BF

1 相交于点 H,线段 ED 与 AF 相交于点 G.. 求证: SEHFG≤ SABCD. 4 如果 ABCD 是一个任意凸四边形,同样结论是否成立?请说明理由.(1994 年中国数学奥林 匹克试题)

C 类例题
例 6 在平面内任给 n(n>4)个点,其中任意 3 点不共线.试证:至少有 C2 n?3 个以上述所给 定点为顶点的凸四边形.(第 11 届 IMO 试题) 分析 由于平面上任何 5 点(其中任意 3 点不共线)中必有 4 点是一个凸四边形的 4 个顶点, 于是通过算两次的方法,利用排列组合知识计算出不同的凸四边形的个数的最小下界,然后 2 用数学归纳法证明此下界超过 C2 n?3.另一种方法是直接找出 Cn?3 个凸四边形. 证法一 由 E.Klein 定理知,平面内任何 5 点(其中任意 3 点不共线)中必有 4 点是一个凸 5 四边形的 4 个顶点,而 n 个点可组成 C5 n个 5 点组,故一共有 Cn个凸四边形(包括重复计数), 而每个凸四边形的 4 个顶点恰好属于 C1 n??4=n?4 个 5 点组,所以,不同的凸四边形的个数不少 于 1 5 C. n?4 n 1 5 下面用数学归纳法证明 C ≥C2 n??3(n≥5). n?4 n 1 5 当 n=5 时, C =C2 n??3=1. n?4 n 1 5 设 n=k 时, C ≥C2 k??3,那么,当 n=k+1 时, k?4 k 1 k+1 C5 k+1 2 k C5 = · ≥ · Ck??3 k +1 (k+1)?4 k?3 k?4 k?3 = = k+1 (k?3)(k?4) (k ??)(k?4) · = 2 2 k?3 k2 ??k?4 (k?2)(k?3) ?2(k?5) 2 = ≥C(k+1) ??3. 2 2
E C

D

B

N M A F

1 5 故对一切 n≥5, C ≥C2 n??3. n?4 n

综上可知,至少有 C2 n??3 个凸四边形. 证法二 以给定点中任意 3 点为顶点可以作一个三角形,设这些三角形中面积最大的一 个为△ABC,过顶点 A、B、C 分别作对边的平行线,3 条平行线相交成△DEF(如图),则 n 个 给定的点全部落在△DEF 的内部或边界上(否则与△ABC 的面积最大矛盾). 除 A、B、C3 点外,另外 n?3 个任意两点 M、N 所决定的直线至多与△ABC 的两边相交 而与第三条边不相交.不妨设 MN 不与 BC 相交(如图),于是 MNBC 为凸四边形,显然,这些 凸四边形互不相同,并且至少有 C2 n??3 个. 说明 组合计数是组合几何的一个重要组成部分,算两次是其中的手法之一. 例 7 求平面上满足条件: (1)三角形的三个顶点都是整点,坐标原点为直角顶点; (2)三角形的内心 M 的坐标为(96p,672p),其中 p 为素数的直角三角形的个数. (2003 年湖南省高中数学竞赛试题) 分析 如图,由于 OM 是直角∠AOB 的平分线,M 的坐标已知,可以利用解析几何和 三角的有关知识求出 OM,OA,OB 的斜率,这样可以设出点 A,B 的坐标,利用切线长相等计算

直角三角形内切圆半径 r 的公式(OA+OB?AB=2r)以及 r=

2 OM 就可得出 A,B 坐标的关系式, 2

再利用质因数的分解就可以获解. 解 设如图所示的三角形为满足条件的 Rt△OAB,则直线 OM 的斜率为 tanα= 7; tanα?1 3 4 直线 OA 的斜率为 tan(α?45o)= 1+tanα = 4;直线 OB 的斜率为?3. 由此可设 A(4t,3t),B(?3s,4s)(s>0, t>0),则 t=4t?3t,s= ?3s+4s 都是正整数. 2 2 设△OAB 的内切圆半径为 r, 则 r= 2 OM= 2 p?96 12+72=5p×96. 又 OA=5t, OB=5s,AB=5 t2+s2. 由 OA+OB?AB=2r,得 5 t2+s2=5t+5s?2×5p× 96. 两边平方,整理得 (t?192p)(s?192p)=2p2×962=211×32×p2. 因 5t>2r, 5s>2r, 故 t?192p>0, s?192p>0. 因此,所求三角形的个数等于 211×32×p2 的正因数的个数,即 当 p≠2,3 时,共有(11+1)(2+1)(2+1)=108 个直角三角形符合条件; 当 p=2 时,共有(13+1)(2+1)=42 个直角三角形符合条件; 当 p=3 时,共有(11+1)(4+1)=60 个直角三角形符合条件. 说明 本题的解法采用层层推进,先从 OM,OA,OB 的斜率出发,再探求 A,B 坐标之间的 关系.进而利用内切圆半径的两种算法使问题的解决架起了桥梁. 例 8 设 n 和 k 是正整数,S 是平面上 n 个点的集合,满足: (1) S 中任何三点不共线; (2) 对 S 中的每一点 P, S 中存在 k 个点与 P 的距离相等. 1 证明:k< + 2n.(第 30 届 IMO 试题) 2 分析 由于 S 中的每一点 P, S 中存在 k 个点与 P 的距离相等,所以考虑以 S 中的每一点为 中心作圆,每个圆上至少有有 k 个点,再利用算两次的方法计算两个端点均属于 S 的线段的 条数,就可以得出不等关系,问题就迎刃而解. 解 依题设,以 S 中的每一点为中心可作 n 个圆,使每个圆上至少有 k 个点属于 S. 我们称两个端点均属于 S 的线段为好线段.一方面,好线段显然共有 C2 n条. 2 另一方面,每个圆上至少有 C2 条好线段, n 个圆共有 n C 条好线段 , 但其中有一些公共弦被重 k k 复计算了. 但每两个圆至多有一条公共弦, n 个圆至多有 C2 n条公共弦(这些弦不一定是好线段), 2 2 2 2 2 故好线段的条数不少于 nCk-Cn.综上所述,得到 Cn≥nCk-C2 n.即 k ?k?2(n?1)≤0. 1+ 1+8(n?1) 1+ 8n 1 所以,k≤ < = + 2n . 2 2 2 说明 (1)本题中第一个条件是多余的; (2)算两次的思想方法在组合数学中经常使用,如果两次都是精确结果,综合起来得到一个 等式;如果至少有一次采用了估算(计算了量的上界或下界),那么,就可以得到一个不等式.
M A x B y

O

情景再现
6. 平面上给定 100 个点,其中任意 3 点可组成三角形,证明至多有 70%的三角形为锐角三角 形.(第 12 届 IMO 试题) 7. 设 M 为平面上坐标为(p×1994,7 p×1994)的点,其中 p 是素数.求满足下述条件的直角三角 形的个数:

(1) 三角形的三个顶点都是整点,而且 M 是直角顶点; (2) 三角形的内心是坐标原点.(1994 年中国数学奥林匹克试题) 8. 平面上有 n≥5 个互不相同的点,每点恰好与其它 4 点的距离为 1,求这样的 n 的最小 值.(2004 年中国国家集训队测试题)

习题 16
1. 在六条棱长为 2,3,3,4,5,5 的所有四面体中最大的体积是多少?证明你的结论.(1983 年全国 高中数学联赛第二试试题) 2.平面上的点集 H 称为好的,如果 H 中的任意 3 点都存在一条对称轴,使得这 3 个点关于这 条对称轴对称.证明: (1)一个好的集合不一定是轴对称的; (2)如果一个好的集合中恰有 2003 个点, 则这 2003 个在一条直线上.(2003 年匈牙利数学奥林 匹克试题) 3.已知一张 n×n (n≥3)的方格纸板,每个单位正方形内有下列四个单位向量之一:↑,↓, ←,→,其中向量平行于单位正方形的边,且过单位正方形的中心.一只甲虫每次根据向量所 指的方向从一个单位正方形爬到另一个单位正方形.如果甲虫从任意一个单位正方形出发,经 过若干次移动以后,又回到出发时的那个单位正方形,其中向量所指的方向不允许甲虫离开 方格纸板. 问是否可能使得任意一行(不包括第一行和最后一行)所有向量的和等于这一行平行于这一行 的所有向量之和, 任意一列(不包括第一列和最后一列)所有向量的和等于这一列平行于这一列 的所有向量之和.(2003 年白俄罗斯数学奥林匹克试题) 4.设正整数 n≥3,如果在平面上有 n 个格点 P1,P2,?,Pn 满足:当|Pi Pj|为有理数时,存在 Pk,使 得|Pi Pk|和|Pj Pk|都是无理数;当|Pi Pj|为无理数时, 存在 Pk,使得|Pi Pk |和|Pj Pk|都是有理数,那么, 称 n 为“好数”. (1)求最小的“好数” ; (2)问:2005 是否为“好数”?(2005 年中国女子数学奥林匹克试题) 5.证明:对 n≥4,每一个有外接圆的四边形,总可以划分成 n 个都有外接圆的四边形.(第 14 届 IMO 试题) 6.在平面上引 4 条直线,使得其中每两条都相交,而任何 3 条不共点(这些直线中的每一条都与其 余的直线有三个交点),试问这样分割的 8 条线段的长度能否分别等于 (1)1,2,3,4,5,6,7,8; (2)不同的正整数值.(1991 年全苏数学奥林匹克试题) 7.在边长为 1 的正方形网格平面上有一个直角三角形, 其所有顶点都是格点, 且三边长均为整 数,证明其内切圆圆心也是一个格点.(1991 年德国数学奥林匹克试题) 8. 平面上已给 7 个点,用一些线段连接它们,使得 (1)每三点中至少有两点相连; (2)线段的条数最少. 问有多少条线段?给出一个