9512.net
甜梦文库
当前位置:首页 >> 高一数学 >>

第14讲 染色问题



第 14 讲 染 色 问 题
本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅助 解题的手段,通过染色,把研究对象分类标记,以便直观形象地解决问 题,因此染色就是分类的思想的具体化,例如染成两种颜色,就可以看 成是奇偶分析的一种表现形式.染色,也是构造抽屉的一个重要方法, 利用染色分类,从而构造出抽屉,用抽屉原理来解题.

A 类 例 题
例 1 ⑴ 有一个 6 × 6 的棋盘,剪去其左上角和右下角各一个小格 ( 边长为 1) 后,剩下的图形能不能剪成17个 1 × 2 的小矩形? ⑵ 剪去国际象棋棋盘左上角 2 × 2 的正方形后,能不能用15个由 四个格子组成的 L 形完全覆盖?





分析 把棋盘的格子用染色分成两类,由此说明留下的图形不能 满足题目的要求.

1

证明 ⑴如图,把 6 × 6 棋盘相间染成黑、白二色,使相邻两格染 色不同.则剪去的两格同色.但每个 1 × 2 小矩形都由一个白格一个黑 格组成,故不可能把剩下的图形剪成17个 1 × 2 矩形. ⑵如图,把 8 × 8 方格按列染色,第 1 , 3 , 5 , 7 列染黑,第 2 、 4 、 6 、 8 列染白.这样染色,其中黑格有偶数个.由于每个 L 形 盖住三黑一白或三白一黑,故15个 L 形一定盖住奇数个黑格,故不可 能. 说明 用不同的染色方法解决不同的问题. 例 2 用若干个由四个单位正方形组成的“ L ”形纸片无重叠地拼成 一个 m×n 的矩形,则 mn 必是 8 的倍数. 分析 易证 mn 是 4 的倍数,再用染色法证 mn 是 8 的倍数. 证明:每个 L 形有 4 个方格,故4|mn.于是 m 、 n 中至少有一个为 偶数.设列数 n 为偶数,则按奇数列染红,偶数列染蓝.于是红格与蓝 格各有 1 1 mn 个,而 mn 是偶数.每个 L 形或盖住 3 红 1 蓝,或盖住 2 2

1 红 3 蓝,设前者有 p 个,后者有 q 个. 于是红格共盖住 3p+q 个即 p+q 为偶数,即有偶数个 L 形.设有 2k个 L 形.于是 mn=2k ×4=8k.故证. 说明 奇偶分析与染色联合运用解决本题.

情 景 再 现
1 .下面是俄罗斯方块的七个图形:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

请你用它们拼出 (A) 图,再用它们拼出 (B) 图 ( 每块只能用一次, 并且不准翻过来用 ) .如果能拼出来,就在图形上画出拼法,并写明七 个图形的编号;如果不能拼出来,就说明理由.
2

(A)

(B)

2 .能否用图中各种形状的纸片(不能剪开)拼成一个边长为75的 正方形?(图中每个小方格的边长都为 1 )请说明理由.

B类 例 题
例 3 ⑴ 以任意方式对平面上的每一点染上红色或者蓝色.证明: 一定存在无穷条长为 1 的线段,这些线段的端点为同一颜色. ⑵ 以任意方式对平面上的每一点染上红色或者蓝色.证明:存在 同色的三点,且其中一点为另两点中点. 分析 任意染色而又要求出现具有某种性质的图形,这是染色问题 常见的题型,常用抽屉原理或设置两难命题的方法解. 证明 ⑴取边长为 1 的等边三角形,其三个顶点中必有两个顶点同 色.同色两顶点连成线段即为一条满足要求的线段,由于边长为 1 的等 边三角形有无数个,故满足要求的线段有无数条. ⑵ 取同色两点 A 、 B ,延长 AB 到点 C ,使BC=AB,再延长 BA 到点 D ,使 AD=AB ,若 C 、 D 中有一点为红色,例如点 C 为红色,则 点 B 为 AC 中点.则命题成立.否则, C 、 D 全蓝,考虑 AB 中点 M , 它也是 CD 中点.故无论 M 染红还是蓝,均得证.
3

说明 ⑴中,两种颜色就是两个“抽屉 ” 三个点就是三个“苹 , 果 ” 于是根据抽屉原理,必有两个点落入同一抽屉. , ⑵中,这里实际上构造了一个两难命题:非此即彼,二者必居其 一.让同一点既是某两个红点的中点,又是两个蓝点的中点,从而陷入 两难选择的境地,于是满足条件的图形必然存在.达到证明的目的. 例 4 ⑴ 以任意方式对平面上的每一点染上红色或者蓝色.证明: 一定可以找到无穷多个顶点为为同一种颜色的等腰三角形. ⑵ 以任意方式对平面上的每一点染上红色或者蓝色.证明:一定 可以找到无穷多个顶点为为同一种颜色的等腰直角三角形. 分析 ⑴同样可以设置两难命题:由于等腰三角形的顶点在底边的 垂直平分线上,故先选两个同色点连成底边,再在连线的垂直平分线上 找同色的点,这是解法 1 的思路.利用圆的半径相等来构造等腰三角形 的两腰,这是解法 2 的思路.利用抽屉原理,任 5 个点中必有三点同 色,只要这 5 点中任三点都是一个等腰三角形的顶点即可,而正五边形 的五个顶点中任三个都是等腰三角形的顶点,这是解法 3 的思路. ⑵连正方形的对角线即得到两个等腰直角 N 三角形,所以从正方形入手解决相题第 2 问. D E ⑴ 证明 1 任取两个同色点 A 、B(设同 H K 红 ) ,作 AB 的垂直平分线 MN ,若 MN 上 A B ( 除与 AB 交点外 ) 有红色点,则有红色三角 形,若无红色点,则 MN 上至多一个红点其余 G F C 均蓝,取关于 AB 对称的两点 C 、 D ,均 M 蓝.则若 AB 上有 ( 除交点外 ) 蓝点,则有蓝 色三角形,若无蓝点,则在矩形 EFGH 内任取 一点K(不在边上 ) 若 K 为蓝,则可在 CD 上取两点与之构成蓝色三角 形,若 K 为红,则可在 AB 上找到两点与之构成红色三角形. 证明 2 任取一红点 O ,以 O 为圆 E 心任作一圆,若此圆上有不是同一直 径端点的两个红点 A 、 B ,则出现红 O O
4

A
(1)

B

C

(2)

F

D

色顶点等腰三角形OAB,若圆上只有一个红点或只有同一直径的两个端 点是红点,则圆上有无数蓝点,取两个蓝点 ( 不关于红点为端点的直径 对称)C、 D ,于是 CD 的垂直平分线与圆的两个交 A 点 E 、 F 为蓝点,于是存在蓝色顶点的等腰三角形 E CDE. B O 证明 3 取一个正五边形 ABCDE ,根据抽屉原 理,它的 5 个顶点中,必有三个顶点 ( 例如 A 、 C D B 、C)同色,则△ ABC 即为等腰三角形. ⑵证明 任取两个蓝点 A 、 B ,以 AB 为一边 A D 作正方形 ABCD ,若 C 、 D 有一为蓝色,则出现蓝 色三角形.若 C 、 D 均红,则对角线交点 E 或红或 E 蓝, 出现红色或蓝色等腰直角三角形.显然按此 作法可以得到无数个等腰直角三角形. ( 由本题也 B C 可以证明上一题. ) 例 5 设平面上给出了有限个点 ( 不少于五点 ) 的集合 S ,其中若干 个点被染成红色,其余点被染成蓝色,且任意三个同色点不共线.求 证:存在一个三角形,具有下述性质: ⑴ 以 S 中的三个同色点为顶点; ⑵ 此三角形至少有一条边上不含另一种颜色的点. 分析 要证明存在同色三角形不难,而要满足第⑵个条件,可以 用最小数原理. 证明 由于 S 中至少有五点,这些点染成两种颜色,故必存在三 点同色.且据已知,此三点不共线,故可连成三角形. 取所有同色三角形,由于 S 只有有限个点,从而能连出的同色三 角形只有有限个,故其中必有面积最小的.其中面积最小的三角形即为 所求. 首先,这个三角形满足条件⑴,其次,若其三边上均有另一种颜 色的点,则此三点必可连出三角形,此连出三角形面积更小,矛盾. 说明 最小数原理,即极端原理.见第十二讲.
5

例 6 将平面上的每个点都染上红、蓝二色之一,证明:存在两个 相似的三角形,其相似比为1995,且每一个三角形的三个顶点同 色. (1995 年全国联赛加试题 ) 分析 把相似三角形特殊化,变成证明相似的直角三角形,在矩形 的网格中去找相似的直角三角形,这是证法 1 的思路.证法 2 则是研究 形状更特殊的直角三角形:含一个角为30 ? 的直角三角形.证明可以找 到任意边长的这样的三角形,于是对任意的相似 l R P S 比,本题均可证.证法 3 则是考虑两个同心圆上三 l 条半径交圆得的三组对应点连出的两个三角形一定 T 相似,于是只要考虑找同心圆上的同色点,而要得 l Q 到 3 个同色点,只要任取 5 个只染了两种颜色的点 就行;而要得到 5 个同色点,则只要取 9 个只染了 两种颜色的点即行. 证明 1 首先证明平面上一定存在三个顶点同色的直角三角形. 任取平面上的一条直线 l ,则直线 l 上必有两点同色.设此两点为 P 、 Q ,不妨设 P 、 Q 同着红色.过 P 、 Q 作直线 l 的垂线 l1 、 l2 ,若 l1 或 l2 上有异于 P 、 Q 的点着红色,则存在红色直角三角形.若 l1 、 l2 上除 P 、 Q 外均无红色点,则在 l1 上任取异于 P 的两点 R 、 S ,则 R 、 S 必着蓝色,过 R 作 l1 的垂线交 l2 于 T ,则 T 必着蓝色.△ RST 即为三 顶点同色的直角三角形. 下面再证明存在两个相似比为1995的相似的直角三角形. 设直角三角形ABC三顶点同色 ( ∠ D A B 为直角 ) .把△ABC补成矩形 ABCD(如图 ) .把矩形的每边都分成 n M E' G E 等分 (n 为正奇数, n>1 ,本题中取 F N H F' n=1995) .连结对边相应分点,把矩形 B C ABCD 分成 n2 个小矩形. P Q AB 边上的分点共有 n+1 个,由于 n 为奇数,故必存在其中两个相邻的分点同色, ( 否则任两个相邻分点
1 2

6

异色,则可得 A 、 B 异色 ) ,不妨设相邻分点 E 、 F 同色.考察 E 、 F 所在的小矩形的另两个顶点E′、F′,若E′、F′异色,则△ EFE′ 或△ DFF′ 为三个顶点同色的小直角三角形.若E′、F′同色,再考察以此二 点为顶点而在其左边的小矩形,….这样依次考察过去,不妨设这一行 小矩形的每条竖边的两个顶点都同色. 同样, BC 边上也存在两个相邻的顶点同色,设为 P 、 Q ,则考 察 PQ 所在的小矩形,同理,若 P 、 Q 所在小矩形的另一横边两个顶点 异色,则存在三顶点同色的小直角三角形.否则, PQ 所在列的小矩形 的每条横边两个顶点都同色. 现考察 EF 所在行与 PQ 所在列相交的矩形GHNM,如上述, M、 H 都与 N 同色,△ MNH 为顶点同色的直角三角形. 由 n=1995 ,故△ MNH ∽△ABC,且相似比为1995,且这两个直 角三角形的顶点分别同色. 证明 2 首先证明:设 a 为任意正实数,存在距离为2a的同色两 点.任取一点 O( 设为红色点 ) ,以 O 为圆心, E F 2a为半径作圆,若圆上有一个红点,则存在距离 为2a的两个红点,若圆上没有红点,则任一圆内 B 接六边形 ABCDEF 的六个顶点均为蓝色,但此六 A 边形边长为2a.故存在距离为2a的两个蓝色点. 下面证明:存在边长为 a , 3 a ,2a的 C D 直角三角形,其三个顶点同色.如上证,存在距 离为2a的同色两点 A 、B(设为红点 ) ,以 AB 为直径作圆,并取圆内接 六边形 ACDBEF ,若 C 、 D 、 E 、 F 中有任一点为红色,则存在满足要 求的红色三角形.若 C 、 D 、 E 、 F 为蓝色,则存在满足要求的蓝色三 角形. 下面再证明本题:由上证知,存在边长为 a , 3 a ,2a及 1995a ,1995 3 a , 1995×2a 的两个同色三角形,满足要求. 证明 3 以任一点 O 为圆心, a 及 1995a 为半径作两个同心圆,在 小圆上任取 9 点,其中必有 5 点同色,设为 A 、 B 、 C 、 D 、 E ,作射 线 OA 、 OB 、 OC 、 OD 、 OE ,交大圆于A′,B′,C′,D′,E′,则
7

此五点中必存在三点同色,设为A′、B′、C′.则 ?ABC 与 ?A′B′C′ 为满 足要求的三角形.

情 景 再 现
3 .以任意方式对平面上的每一点染上红色或者蓝色.证明:一定 存在一个矩形,它的四个顶点同色. 4 .以任意方式对平面上的每一点染上红色或者蓝色.证明:一定 可以找到无穷多个顶点全为同一种颜色的全等三角形. 5 .图中是一个 6 × 6 的方格棋盘,现将部分 1 × 1 小方格涂成 红色。如果随意划掉 3 行 3 列,都要使得剩下的方格中一定有一个是红 色的,那么至少要涂多少个方格? 6 .有两个同心圆,圆上的每个点都用红、蓝、黄三色之一染 色.试证明:可以分别在每个圆上找到同色的三个点连成圆的内接三角 形,且这两个三角形相似.

C类 例 题
例 7 把平面上每个点都以红、黄两色之一着色.求证:一定存在一 个边长为 1 或 3 的正三角形,它的三个顶点是同色的. 分析 边长为 1 及 3 的三角形在半径为 1 的圆内接正六边形中出 现,故应设法在这样的圆内接正六边形内找满足要求的三角形.以红点 M 为圆心, 1 为半径作圆, 6 等分此圆,若其中没有红点,则存在边长 为 3 的黄顶点三角形,若有红点 R ,则与之相邻的两分点中有红点则 有边长为 1 的红顶点三角形,若与 R 相邻的两分点均黄,则考虑直径 RQ 的另一端点 Q ,若为黄则可证.故应相距为 2 的两点 R 、 Q ,这样 就可构造两难命题了. 证明: 1 ? 任取一染成红色的点 P ,以 P 为圆心, 1 为半径作圆, 如果圆上及圆内的点都是红色,则存在边长为 1 及 3 的三角形,其三 个顶点同为红色.
8

若圆上及圆内的点不全染成红色.则存在圆上或圆内一染成黄色的 点 Q , |PQ| ≤ 1 .作△PQR,使 PR=QR=2 ,则 R 必与 P 、 Q 之一染色 不同.设 R 与 Q 染色不同,即 R 染红色. 2 ? 取 QR 中点 M ,则 M 必与 Q 、 R 之一同 R S 色.设与 R 同色,即同为红色.以 RM=1 为一边,作 T 正三角形△RMS、△RMT.若 S 、 T 中任一点染红, M 则存在边长为 1 的红色顶点三角形.若 S 、 T 都为黄 色,则与 Q 组成边长为 3 的黄色顶点三角形. 说明 把问题归结为相距为 2 的异色两点.
P Q



例 8 在一张 100×100 的方格纸内,能否把数字 0 , 1 , 2 分别放在 每一个小方格内 ( 每格放一个数 ) ,使得任意由 3×4(及 4×3)小方格构成 的矩形中都有 3 个 0 , 4 个 1 及 5 个 2 . 分析 3× 4 方格由 4 个 3 × 1 方格组成,因此研究这样的方格的可 能填法. 证明 设存在这样的填法.两个图形中填入的 0 、 1 、 2 的个数如 果完全相同,就称这两个图形是填法相同的图形. 1 ? 现在研究图⑴中的 4 个 3×1 或 1×3 矩形 ( 阴影部分 ) ,由于它们都与中心的 3×3 矩形组成 3×4 矩形,若存在满足要求的填法时,它们的填法 必相同. 2 ? 对于任一 3×n 矩形 ( 如图 2 中部 ) ,比较 两个只相错一个 1×3 矩形的两个 3×4 矩形,知,同 图 1 色的 1×3 矩形的填法应相同.即染色是周期出现 的. 3 ? 现考虑1×12矩形, 如图 2 ,根据⑴的结果可 知,图 2 中同色的 1×3 或 3×1 矩形的填法相同.于是 每个1×12矩形应与一个 3×4
图 2

9

矩形的填法相同.即图中一面的1×12矩形含有 4 个 1×3 矩形,分别有 4 种颜色. 4 ? 但1×12矩形中填了 5 个 2 ,从而必有某个 1×3 矩形中填了 2 个 2 .不妨设黄色的 1×3 矩形中填了 2 个 2 .于是用下面的1×12矩形的染 色法知每个1×12矩形中至少有 6 个 2 . 由 3 ? 、 4 ? 矛盾,知这样的填法不存在.

情 景 再 现
7 .⑴设有4×28个小方格,给每个小方格都染上红、蓝、黄三种颜 色中的一种.试证明:至少存在一个矩形,它的四个角的小正方形同 色. ⑵ 4×19 小方格如上染三色,试证:至少存在一个矩形,它的四个 角的小正方形同色. 8 .一个等边三角形的三边上所有的点 ( 包括顶点 ) 都染成红色或 蓝色之一,求证:必可找到此三角形边上的三个同色点,使这三个点是 直角三角形的三个顶点.

习 题 14
1 .以任意方式对数轴上的每一坐标为整数的点染上红色或者蓝 色.证明:对任意正整数 n ,都能找到无数个点,这些点同色且坐标能 被 n 整除. 2 .以任意方式对平面上的每一点染上红色或者蓝色.证明:一定 可以找到无穷多个顶点全为同一种颜色的三角形. 3 .对正整数列按照以下方法由小到大进行染色:如果能够表示为 两个合数的和,则染成红色,否则染成蓝色.所有被染成红色的数中由 小到大数的第1994个数是多少? 4 .把一个马放入 4 × 8 的国际象棋棋盘的任何一格上,能否把 它连跳32步,使得马跳遍棋盘上每一格并回到最初位置?
10

5 .能否用一个 “ 田 ” 格与15个 1×4 矩形纸片盖满 8×8 棋盘? 6 .用右图中 4 个小方格组成的 “L” 形若干个盖 住了一个 4×n 矩形,那么, n 一定是偶数. 7 .一个立方体的八个顶点分别染上红色或绿色, 六个面的中心也都分别染色,若一个面的四个顶点中有 奇数个绿点 , 则这个面的中心也染成绿色 , 否则就染成 图 红色 . 求证 : 这样得到的十四个色点不可能一半是红色 一半是绿色 . 8 .把 4 个同心圆的圆周各分成 100 等分.把这 400 个分点染成 黑、白两色之一,使每个圆上都恰有50个黑点及50个白点.证明:可以 适当旋转这 4 个圆,使得能够从圆心引出的13条射线,每条射线穿过的 4 个染色相同的分点. 9 .将一个三角形ABC的三个顶点分别染上红、蓝、黑之一,在 ?ABC 内部取若干点也任意涂红、黑、兰三色之一,这些点间 ( 没有三 点共线 ) 连有一 些线段,把大三角形分成若干互相没有重叠部分的一 些小三角形 . 求证 : 不论怎样涂,都有一个小三角形,其三个顶点涂的 颜色全不同 . 10.一个棱柱以五边形 A1A2A3A4A5 及 B1B2B3B4B5 分别为上下底 , 这 两个多边形的每一条边及线段AiBj(i,j=1,2,3,4,5)均涂上红色与绿色 , 每个 以棱柱的顶点为顶点 , 以涂色线段为边的三角形都有两边颜色不同 , 求 证 : 上底与下底10条边的颜色相同. 11.将凸2003边形的每个顶点都染色,且任意相邻两个顶点都异 色.试证:对上述任何一种染色法,都可以用互不相交于内点的对角线 将多边形完全剖分成若干三角形,使得剖分中所用每条对角线的两端点 都不同色. 12. 100×100 小方格表中每一个都被染成 4 种颜色之一,使得每行 与每列恰有每种颜色的小方格各25个.证明:可以在表中找到 2 行与 2 列,它们交得的 4 个小方格所染的颜色互不相同. (2000 第26届俄罗斯 数学奥林匹克 )

11

本节“情景再现”解答: 1 .解 将 (A) 的方格染成黑白两色,使相邻的方格都不同色 ( 图 (C)) ,则此图中黑白方格的个数相等,但如将⑴—⑺染色,则⑴—⑹都 可染成黑白相间的两黑两白,但⑺只能染成一黑三白或三黑一白,于是 ⑴—⑺染色后黑白方格数不等.所以 (A) 图不能被⑴—⑺完全覆盖. 而图 (B) 则因染 色后黑白格相差 1 (3) (7) 格,故有被盖住的可 (4) (2) 能.经试验,可如图 (5) (6) (D) 沿粗线分开的方 (1) 格分别用⑴—⑺盖 (C) (D) 住. 2 .解 把75×75方格与图中给出的 4 种形状的小方格都染成黑白 两色,使任何相邻的格子染色不同. 由于75×75方格的格子数为奇数,故其黑白格子的个数相差 1 个. 但这四种形状的方格的染色中,前两种黑白格子数相等,第三种染 的黑白格子数分别为 4 与 1( 黑 4 白 1 或者白 4 黑 1),第四种形状染的黑 白格子数分别为 5 与 2 ,这两种格子的黑白格子数相差 3 ,于是用这四 种形状中的任何几种覆盖住的方格,应盖住相等的黑白格或盖住的黑白 格相差 3 的整数倍,不可能只相差 1 .所以本题是不可能盖住的. 3 .证明:取 3 行 7 列共21个点组成矩形网格.考虑每列 3 个点的 染色方式共有 8 种,若有某列 3 点全染红色,则只要其余 6 列中有某列 有 2 个点染红,则存在四个顶点都是红色 的矩形,若有某列 3 个点全蓝也同理. 若 7 列中没有全红、全蓝两种情况, 则 7 列的染色方式只有 6 种,必有两列染 色方式相同,此二列中有四点满足要求. 4 .证明 以 1 为边长作正五边形,其五个顶点染二色,必有三个 顶点同色.于是出现同色三角形,由于正五边形中的三角形只有两种形 状,而边长为 1 的五边形有无穷多个,故由抽屉原理知,至少有一种形
12

状的 ( 三个顶点同色的 ) 三角形有无数个.取这种形状的顶点同色的三 角形集合,该集合有无穷多个元素.但这无数个三角形均全等,于是据 抽屉原理,必有其中一种颜色的顶点的三角形有无穷多个. 5 .分析 当涂红格少于或等于 6 时,只要划去时,先划去涂有红 格的 3 行,则余下的红格至多还有 3 格,再划去有涂红格的列(当然不 超过 3 列)则所有的涂红格都被划去了. 仿此,当涂红格少于或等于 9 格时,由于这个图 形只有 6 行,故总有某些行的涂红格不止 1 格,首先 划去涂红格至少 2 格的某一行,余下 5 行中,如涂红 的格子仍不止 5 格,则必有某行的不止 1 个涂红格, 再划去至少有 2 个涂红格的行,从第二步起,如涂红 格不足 3 格时,则任意划去某行.这样,当涂红格不多于 9 格时,总可 以划去 3 行,使余下涂红格不多于 3 格,这时划去有涂红格的列,则总 可以使余下方格中没有红格. 故,要保证划去 3 行 3 列后余下格中一定有涂红格,就一定要涂至 少10格. 当涂红格为10格时,可如图的涂法,此时划去 3 行后至多划去 6 个 涂红格,余下至少 4 个涂红格在至少 4 列中,从而任意划去 3 列后至少 还要余下 1 个涂红格. 6 .证明 按两个圆的半径的大小称这两个圆为大圆与小圆. 19 在大圆上任取19个点,这19个点都染了三种颜色,故其中必有? ? ?3? +1 = 7 个点同色,作过这 7 个同色点的半径,交小圆于 7 点.于是, 7 这 7 个点中必有? ? ?3? +1 = 3 个点同色.这三点不可能在同一条直线

上,可连成一个三角形,过这三个点的半径与大圆的三个交点再连成三 角形,这两个三角形就满足要求. 7 .证明 ⑴ 第一行中必有一种颜色有至少10个设为红,把它们 换到前10列,下面 3 行的前10列中,若有某一行有 2 个红格,则可得 证.设每行至多有 1 个红格.于是至少有 7 列中没有红色格.这个 3 ×
13

7 矩形可证 ( 可见《情景再现》第 3 题的证明 ) . ⑵ 由于一列 4 格染成 3 色,必有某色至少染 2 格.每种颜色染 2 格的方案都各有 6 种,故共有18种可能.在19列中,必有两列染两格的 方法相同.故证. 8 .证明 分别在 AB 、 BC 、 CA 上取点 A D 、 E 、 F ,使 AD=BE=CF= 1 AB .易证 DE ⊥ 3
D

F BC , EF ⊥ AC , FD ⊥ AB .由于 D 、 E 、 F 三点染成红、蓝两色,故必有两点同色,设 D 、 E B C K E 两点染成红色.则若 BC 上除点 E 外还有一点 K 染 成红色,则出现红色顶点直角△DEK.若 BC 上除 E 外全染蓝色.则 AB 与 AC 上除点 D 外有任一点染蓝,就出现蓝色三 角形.如果 AB 、 AC 上没有蓝色点.则△ADF即为红色顶点三角形.

“习题14”解答: 1 .证明:坐标为 n 的倍数的点有无数个,染成两色,则必有一种 颜色有无穷多个. 2 .证明 任取两个红点 A 、 B 及两个蓝点 C 、 D ,平面上不在直 线 AB 及 CD 上的点有无数个,于是至少有一种颜色染了无数个点,即 有无数个同色三角形. 3 .解 1, 2 , 3 , 4 , 5 , 6 , 7 , 9 ,11都不能写成两个合数 的和. 由于 4k=4+4(k - 1) , 4k+2=4+2(2k - 1) ,故不小于 8 的偶数都能写 成两个合数的和. 由于 2k+1=9+2k - 8=9+2(k - 4),故不小于13的奇数均可以写成两 个合数的和.所以,第1994个数是2003. 4 .解 这半个棋盘有 4 行,把上下两行的格子称为外格,中间两 行的格子称为内格.外格与内格的格子数一样多. 一只国际象棋的马不能一步从外格跳到外
14

格,所以如果马从某一格开始每格正好跳一次地跳遍棋盘,并且最后回 到起点,它就不能从内格跳到内格(否则内格就会比外格多)这就说 明 ,马只能外格与内格交替地跳.现在把半个国际象棋棋盘按右图所 示染色.显然,马从外格跳到内格时是跳到同色的格子上去,而从内格 跳到外格时也是跳到同色的格子上.这样一来,按上述跳法,马就只在 同色的格子之间跳动,这就说明,马是不能从这半个棋盘上的任一格出 发,跳遍棋盘上的所有格子并回到起点处的.故这样的跳法是不存在 的. 5 .把 8×8 矩形按右图染成黑白两色,则一个 “ 田 ” 字形必盖住 3 白 1 黑格或 3 黑 1 白格,而一个 1×4 矩形盖住 2 白 2 黑格.故本题无 解. 6 .把 4×n 方格按右图的方法染成黑白两色,则任一 “L” 形必盖住 3 白 1 黑或 3 黑 1 白,如 n 为奇数,则盖住这个 图形的 “L” 形个数也必为奇数,于是盖住的白格 与黑格也都是奇数个.但图中的白格与黑格数都 是偶数.故不可能盖住. 7 .证明 设此立方体的六个面中有 x 个面顶点是 4 红, y 个面的 顶点是 2 红 2 绿, z 个面的顶点是 4 绿;有 k 个面顶点是 3 红 1 绿, h 个面顶点是 1 红 3 绿. 统计每个面上在顶点处的绿点数:2y+4z+k+3h,每个顶点都在 3 个 面上统计了一次,故顶点上的绿点共有 1 (2y+4z+k+3h) 个,中心的绿点 3

共有 k+h 个.若这14个点中,红绿各一半,则得 1 (2y+4z+k+3h)+k+h=7 .即(2y+4z+k+3h)+3k+3h=21, 3 ?2y+4z+4k+6h=21 .这是不可能的.故证. 8 .证明 把圆旋转 2π 称为一次旋转,再把四个同心圆从内到外 100

依次称为圆Ⅰ、Ⅱ、Ⅲ、Ⅳ. 先过圆心 O 任作一条射线 OX ,把四个圆旋转,使每个圆都有一个
15

分点在 OX 上,固定圆Ⅰ,其上的某个分点 A 在 OX 上,旋转圆Ⅱ,使 其上每个点都与 OX 对齐一次,记下圆Ⅱ在每个位置时两圆同色点对齐 的点对个数,由于圆Ⅱ的每个点都与圆Ⅰ的点 A 对齐 1 次,故点 A 在旋 转过程中共与圆Ⅱ的同色点对齐了50次,每个圆Ⅰ的点都是这样,故在 圆Ⅱ的旋转过程中,共有50×100次同色点对齐.于是至少有一次,同色 点对齐的点对数不少于? 50×100? ? 100 ? =50次.在圆Ⅱ的 100 个位置中,必有

某个位置使圆Ⅰ、Ⅱ的同色点对齐的个数最多.把圆Ⅱ固定于该位 置.此时两圆至少有50个同色点对齐.把异色点对齐的点对去掉,则两 圆上至少留下对齐的50对同色点. 再把圆Ⅲ旋转,同上,把圆Ⅲ与圆Ⅱ的同色点对齐个数最多的位置 固定,此时圆Ⅱ与圆Ⅲ至少有? 50×50? ? 100 ? =25个同色点对是对齐的,把这 25×50? ? 100 ?

些点对留下,其余点去掉.再旋转圆Ⅳ,同样,把圆Ⅳ与圆Ⅲ的同色点 对齐个数最多的位置固定,此时圆Ⅳ与圆Ⅲ至少有? +1 =13个

同色点对是对齐的. 即此时四个圆至少有13个同色点是对齐的,从圆心引穿过这些对齐 的同色点的射线至少有13条. 9 .解法 1 :按顶点颜色分类,三角形共有10类:三红,两红一 解法 蓝,两红一黑,一红两蓝,一红两黑,红蓝黑,三蓝,两蓝一黑,一蓝 两黑,三黑. 按线段两端颜色分类,线段共有 6 类:红红,红蓝,红黑,蓝蓝, 蓝黑,黑黑. 现在统计两端分别为红、蓝的边,在两红一蓝或两蓝一红这两类三 角形中,每个三角形都有 2 条红蓝边,每个红蓝黑三角形都有 1 条红蓝 边,设前两类三角形共有 p 个,后一类三角形共有 q 个.则两端红蓝的 边共有2p+ q 条. 而每条两端红蓝的边,在大三角形内的红蓝边设有 k 条,每条都被 计算了 2 次,大三角形的红蓝边有 1 条,计算了 1 次.故
16

2p+ q =2k+ 1 ,于是 q≠0 ,即红蓝黑三角形至少有 1 个. ( 注:统计两端不同色的边都可以 ) 解法 2 在每个划出的小三角形内取一个点,在三角形形外也取一个 点.如果两个三角形有一条红蓝的公共边,则在相应点间连一条线.于 是得到了图 G ,此时,两红一蓝或两蓝一红的三角形都是图 G 的偶顶 点,而红蓝黑三角形则对应着图 G 的奇顶点,大三角形外的那个顶点也 是奇顶点,由奇顶点的成对性,知图 G 中至少还有一个奇顶点,于是, 至少还有一个红蓝黑三角形. 10.证明 首先证明此棱柱的上底面的棱颜色相同.否则必有两条 相邻边颜色不同.不妨设A1A5 为红,A1A2 为绿. 5 条线段 A1Bi(i=1 , 2 , 3 , 4 , 5) 中必有 3 条同色.设有 3 条同 为红色.这 3 条红色的线段中,总有两条是向相邻的两个顶点引出的, 例如A1B1 、A1B2 都为红色.于是在△ A1B1B2 中B1B2 必为绿色. 又在△ A1A5B1 及△ A1A5B2 中,A5B1 及A5B2 均必 A5 为绿色.这样就得△ A5B1B2 全为绿色.矛盾.这说 A1 A4 A2 明上底面的 5 条棱同色. A3 同理,下底面的 5 棱也同色. 下面再证明,上下底面10条棱颜色全同.反设 B5 B4 B1 上底面 5 条棱钱红,下底面 5 条棱全绿.由上证, B3 B2 A1B1 、A1B2 不能全红,但也不能全绿,故必一红一 绿,设A1B1 红,则A1B2 绿,同理得,A1B3 红, A 1B4 绿,A1B5 红,此 时,△ A1B1B5 又出现上证情况.故得证. 11.证明 对于 n = 3 的情况,显然此时只有惟一的三角形且没有 对角线,其三个顶点异色,故满足要求. 设对于 n =2k- 1 ,命题成立.对于 n =2k+1,取多边形的一个顶 点 A ,与 A 相邻的两个顶点异色,若这样的顶点 A 不存在,即与每个顶 点相邻的两个顶点都同色,则可得此多边形的每个顶点都同色. 连此异色的两个顶点,则把原多边形分成一个满足要求的三角形及 一个凸2k边形.若此凸2k边形存在一个顶点 B ,其相邻的两个顶点异 色,则再连此二顶点,又把这个2k边形分成一个三角形及一个凸2k- 1
17

边形,其相邻顶点异色,于是命题成立,若此凸2k边形中不存在满足上 述要求 ( 相邻两个顶点异色 ) 的顶点,则此多边形的顶点只能是相间地 染成两种颜色.此时回到原凸2k+1边形,其顶点 A 与此两种颜色的顶点 相邻,故它染了第三种颜色,把 A 与其余所有顶点连都对角线.则把这 个凸2k+1边形分成了2k- 1 个三角形满足要求.故 n =2k+1时命题也成 立.综上可知,命题对于一切奇数个顶点的凸多边形成立,从而对2003 边形成立. 12.解 设 4 种颜色为 A 、 B 、 C 、 D ,计算同一行的“异色对” 2 数,共有 C 4 ×252 = 6×252 个“异色对 ” 所以各行共有 100×6×252 个 . “异色对 ” . 而每个“异色对”的两小格都在不同的列中,不同的“列对”数共 2 有 C 100 对. 于是必有某个“列对”中有? 100×6×252-1? +1 =76个异色对. ? 99×50 ?

现考虑这 2 列,76行所成的76×2矩阵:其同行两格染色不同.且每 列中染某一色的格子至多25格.如果 {A , B} 与 {C , D} 出现在两 行中,则已证;同样,若 {A , C} 与 {B , D} 出现在两行中,或 {A , D} 与 {B , C} 出现在两行中,问题也解决.设此三种组合 中,每种都至多出现其中的一对.则这三种对子中只能出现:① {A , B} 、 {A , C} 、 {A , D} ;② {A , B} 、 {A , C} 、 {B , C}( 或换成同组中另一对 ) . 对于第一种情况,由于每行中都出现 A ,故共有76个 A 出现在此二 列,至少有一列中 A 的个数有? 76-1? ? 2 ? +1 =38个,第二种情况,由于

只出现 A 、 B 、 C 三种颜色,故任一列中总有某种颜色出现至少

?76-1? ? 3 ?
证.

+1 =26个,均与“每列中同色方格不超过25个”矛盾.故

18



更多相关文章:
2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题
2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题_学科竞赛_高中教育_教育专区。第 14 讲 染色问题本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅...
...提优教程》教案:第14讲 染色问题
2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题 隐藏>> 第14 讲 染色问题本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅助解题的手段,通过染色...
...江苏省2012高中数学竞赛 第14讲 染色问题教案
思科数学【提优教程】江苏省2012高中数学竞赛 第14讲 染色问题教案_金融/投资_经管营销_专业资料。思科数学【提优教程】江苏省2012高中数学竞赛讲义 高中数学培优第...
竞赛讲座 14染色问题与染色方法
竞赛讲座,共35讲.隐藏>> 竞赛讲座 14 -染色问题与染色方法 染色问题与染色...2. (第 49 届苏联基辅数学竞赛题)在两张 1982×1983 的方格纸涂上红,黑...
数学奥林匹克竞赛讲座14染色问题与染色方法
数学奥林匹克竞赛讲座14染色问题与染色方法_学科竞赛...例6 (第 6 届国际数学奥林匹克试题)有 17 位...3. 有九名数学家,每人至多会讲三种语言,每三名...
小学奥数专题15:染色问题
小学奥数专题15:染色问题_学科竞赛_小学教育_教育专区。专题 14 染色问题 1....但是对于一种满足要求跳法,在两种染色方式下第奇数步跳入的格子的全体 是不同...
小学奥数染色与操作问题教师版
第十一讲:染色与操作问题一、染色问题这里的染色问题不是要求如何染色,然后问有...不然无法再往小瓶中倒水的. 【例 14】 老师在黑板上画了 9 个点,要求同学...
简单的染色问题
简单的染色问题_数学_高中教育_教育专区。1 / 14 ...(第 29 届俄罗斯数学奥林匹克) 某国有 N 个城市...原结论成立. 6 / 14 平面几何选讲——反演变换 ...
竞赛讲座14
竞赛讲座 14 -染色问题与染色方法 1. 小方格染色问题 最简单的染色问题是从一...竞赛讲座 14染色问题与染... 8页 免费 七数培优竞赛讲座第14讲... 8页 ...
第11讲.染色与操作问题.学生版_图文
第11讲.染色与操作问题.学生版_学科竞赛_小学教育_教育专区。小学奥数,小学奥数...5 例题 5 右图是由 14 个大小相同的方格组成的图形. 试问 能不能剪裁成 7...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图