高三数学堂专题讲座4

2024年2月29日发(作者：)

高三数学第二课堂专题讲座

组合数学题选讲

【第四讲 染色问题】 （2001年10月9日）

〖知识概要〗

染色问题实际上是对集合元素进行分类的问题，但染色可以使分类更直观，更形象。

常见的染色问题主要有两大类：一类是借助于染色方式去解决问题，其过程简捷，条理清晰；另一类问题的条件是用染色的方式给出的，使得问题别致，新颖。染色包括对区域（如方格，三角形等）、线段、点进行染色。常用的数学思想方法是：整体性思想；抽屉原则；极端原则；数学归纳法；构造思想等。

〖例题选讲〗

例1 求证：世界上任何6人中总可以找到三人，他们互相认识或互相不认识.

证明：首先把任何两人间用线段相连，且互相认识的两人间用红色线段，互不认识的两从间用蓝色线段。这样某人A与其他5人A1,A2,A3,A4,A5间存在有5条线段，因为5＝2×2+1，由抽屉原则，必存在3条同色线段，不妨设AA1,AA2,AA3同为红色，如果A1,A2,A3三人中有两人互相认识，则命题得证，如果A1,A2,A3三人互不认识，则命题也得证。

类题 有17位科学家，其中每一位和其他所有人通信，他们在通信中只讨论3个问题，而且每两位科学家之间只讨论一个问题。试证明，至少有3位科学家相互之间只讨论一个问题。

例2 某班有49名学生，坐成七行七列，每个座位的前后左右均称为它的邻座，问是否可以使全班每个同学都离开自己的座位坐到邻座上去？

解： 把7行7列的座位转化成7×7的方格表，每

个格子代表一个座位, 然后将这个7×7方格

表染色，把任意两相邻格只染一格为红色

（如图）。要使每个同学都离开自己的座位

坐到邻座去，即要从白色格进入红色格或

从红色格进入白色格。而红色格共24个，

白色格共25个，故此目标不能实现。

法2：将方格编号后，进行奇偶性分析。

例3 证明：平行四边形能够被直径不小于较长对角线的圆所覆盖.

证明：如图，设BD是平行四边形ABCD的一条较长的对

A P D

角线，且AC与BD交于O.

在平行四边形的边界上任取一点P，连OP，

O

因为BD＞AC，∠OAD＞∠ODA，

所以在△AOP中，∠OPD＝∠OAD+∠POA

B C

＞∠OAD＞∠ODA

从而OP≤OD，当P为顶点B或D时，等号成立。

因此，以O为圆心，OD为半径的圆能覆盖平行四边形ABCD。

例4 证明：三个边长为1的正方形纸片一定可以覆盖一个边长是5的正方形纸4片.

证明：如图，将第一个边长为1的正方形EFGH纸片覆盖在

R

51边长为的正方形ABCD的右下角，则FC＝AH＝。

44D(S) C

将第二个边长为1的正方形PQRS纸片的顶点S和顶

点D重合，使QR边经过点C。设PQ交BC于

G F Q

M

315 点M，因为CR＝1，所以CQ＝。

444P

CM＞CQ＝FC，即点F被正方形PQRS纸片覆盖。

A H B（E）

32 又sinCDR，所以∠CDR＜。

524从而∠CDP＞，即正方形PQRS纸片完全覆盖梯形CDGF。

4同理，由图形的对称性可知，第三个正方形完全覆盖梯形ADGH。

5综上所述，三个边长为1的正方形纸片一定可以覆盖一个边长是的正方4形纸片.

例5 证明：用15块大小是4×1的矩形和一块2×2的矩形不能恰好覆盖8×8的矩形.

证明：将8×8的矩形染色（如图）。

由于15块大小是4×1的矩形和一块2×2的

矩形的面 积之和等于8×8矩形

的面积，所以绝对不能出现重叠覆盖。每一个

4×1的矩形恰好盖住2个红色矩形，而每一个

2×2矩形恰好盖住一个红格或3个红格，所以

15个大小是4×1的矩形和一个2×2的矩形或

者盖住31个红格或者盖住33个红格，而8×8

的矩形中有32个红格，从而不可能全部盖住红格。

就是说，用15块大小是4×1的矩形和一块2×2的矩形 不能恰好覆盖8×8的矩形.

例6 在平面上给定100个点。证明：可以用若干个互不相交的圆来覆盖它们，并且这些圆的直径之和小于100，任何两个圆之间的距离大于1.（两个点集之间的距离是指从每个点集中各取出一点为端点的线段的最短距离）

证明：以每个给定的点An(n1,2,,100)为圆心，r为半径作圆。这些

· ·

AiAj圆中，每一对相交的圆都可以用覆盖这两个圆且半径不超过这

两个圆的半径之和（2r）的圆来代替（如图），直到得出k(k100)

个互不相交的圆，这k个圆包含所有给定的点和原来那些半径为

r的圆，且它们的直径之和不超过200r。

2

把这k个圆的半径都减小某一个数a（a

从而只要找到两个数r，a，使200r-2a＜100，2a＞1，就得到了满足题意1111的若干个圆，为此，取r即可。

,a22002400

例7 在边长为1000的正方形内互不重叠地放置着4500个直径为的圆。证明：可以在这个正方形内放置60个10×20的矩形，使得这些矩形和圆中任何两个图形均互不重叠.

10001000证明：在边长为1000的正方形内划出4560个

10.520.5边长平行于正方形边的×的矩形。由于已经放置

了直径为的圆共4500个，因此，在这4560个矩形中

至少有60个矩形，在它们的内部不含有这些圆的圆心。

如图，

3例8 已知n个点组成的点集M的直径为1。证明：可以用一个半径为的圆3覆盖M.

例9 证明：可以将平面上的每个点染上7种颜色中的一种，使得没有两个同色的点距离为1.

例10 已知若干红色的点和若干蓝色的点，将它们的某些点连成线段. 如果在与P点相连的点中，与P点颜色不同的点多于一半，则称P为“奇点”若P为“奇点”，则改变P点的颜色（原来是红色的变为蓝色，原来是蓝色的变为红色）. 证明：经过有限次这样的变换，一个“奇点”也没有.

例11 给平面上每一点染成红色或蓝色。证明：必存在边长为1或3的正三角形，它的三个顶点同色.

证明：假设不存在边长为1且顶点同色的正三角形，对于边长为1且顶点异色的正三角形ABC，不妨设A、B两点异色，以AB为底做一个腰为2的等腰三角形ABD，那么不管D为何色，A、D和B、D必有一对异色，不妨设A为红色，D为蓝色，取AD的中点E，不妨设E为红色，则以AE为边所做的两个正三角形AEG，AEH都不是同色三角形，所以G、H均为蓝色，从而△DGH是边长为3的正三角形，且它的三个顶点同色.

例12 将平面上的每个点染上2000种颜色中的一种。再任意给定三角形T，证

明：可以在平面上找到一个与T全等的三角形，在它的每两条边上都有颜色相同的点（不包括顶点）。