当前位置:首页 >> 学科竞赛 >> 2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题

2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题


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

A 类例题
例 1

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

例 1(!)

例 1(2)

分析 把棋盘的格子用染色分成两类,由此说明留下的图形不能满足题目的要求.
[ 来 源:Z#xx#k.Com] [来源:学科网 ZXXK]

[来源:学*科*

网]

证 明 ⑴如 图, 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 数,则按奇数列染红,偶数列染蓝.于是红格与蓝格各有2mn 个,而2mn 是偶数.每个 L 形 或盖住 3 红 1 蓝,或盖住 1 红 3 蓝,设前者有 p 个,后者有 q 个. 于是红格共盖住 3p+q 个即 p+q 为偶数,即有偶数个 L 形.设有 2k 个 L 形.于是 mn=2k ×4=8k.故证.

说明 奇偶分析与染色联合运用解决本题.

情景再现
1.下面是俄罗斯方块的七个图形: 请你用它 们拼出(A)图, 再用它们拼出 (6) (3) (4) (5) (7) (2) (1) (B)图(每块只能 用一次,并且不准翻过来用).如果能拼出来,就在图形上画出拼法,并写明七个图形的编号; 如果不能拼出来,就说明理由.

(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 染红还是蓝,均得证. 说明 ⑴中,两种颜色就是两个“抽屉” ,三个点就是三个“苹果” ,于是根据抽屉原理, 必有两个点落入同一抽屉. ⑵中,这里实际上构造了一个两难命题:非此即彼,二者必居其一.让同一点既是某两 个红点的中点,又是两个蓝点的中点,从而陷入两难选择的境地,于是满足条件的图形必然

存在.达到证明的目的. 例 4 ⑴ 以任意方式对平面上的每一点染上红色或者蓝色. 证明: 一定可以找到无穷多个 顶点为为同一种颜色的等腰三角形. ⑵ 以任意方式对平面上的每一点染上红色或者蓝色.证明:一定可以找到无穷多个顶点 为为同一种颜色的等腰直角三角形. 分析 ⑴同样可以设置两难命题:由于等腰三角形的顶点在底边的垂直平分线上,故先选 两个同色点连成底边,再在连线的垂直平分线上找同色的点,这是解法 1 的思路.利用圆的 半径相等来构造等腰三角形的两腰,这是解法 2 的思路.利用抽屉原理,任 5 个点中必有三 点同色,只要这 5 点中任三点都是一个等腰三角形的顶点即可,而正五边形的五个顶点中任 三个都是等腰三角形的顶点,这是解法 3 的思路. ⑵连正方形的对角线即得到两个等腰直角三角形,所以从正方形入手解决相题第 2 问. ⑴ 证明 1 任取两个同色点 A、B(设同红), 作 AB 的垂直平 N 分线 MN, MN 上(除与 AB 交点外)有红色点, 若 则有红色三角 D E 形, 若无红色点, MN 上至多一个红点其余均 则 蓝,取关于 AB H K 对称的两点 C、D,均蓝.则若 AB 上有(除交点 外)蓝点, 则有蓝 A B 色三角形,若无蓝点,则在矩形 EFGH 内任取 一点 K(不在边上) 若 K 为蓝,则可在 CD 上取两点与之构成蓝色 三角形,若 K 为 G F C 红,则可在 AB 上找到两点与之构成红色三角 形. M 证明 2 任取一红点 O,以 O 为圆心任作一 圆,若此圆上有 不是同一直径端点的两个红点 A、B,则出现红 色顶点等腰三角 形 OAB, 若圆上只有一个红点或只有同 一直径 的两个端 E 点是红点,则圆上有无数蓝点,取两个 蓝点(不关于红点 为端点的直径对称)C、D,于是 CD 的 垂直平分线与圆的 O O 两个交点 E、F 为蓝点,于是存在蓝色 顶点的等腰三角 A 形 CDE. D B C A F E 证明 3 取一个正五边形 ABCDE, 根据抽屉原理, (1) B (2) O 它的 5 个顶点中, 必有三个顶点(例如 A、 B、C)同色,则 △ABC 即为等腰三角形. C D ⑵证明 任取两个蓝点 A、B,以 AB 为一边作正 方形 ABCD, A D 若 C、D 有一为蓝色,则出现蓝色三角形.若 C、D 均红, 则对角 线交点 E 或红或蓝, 出现红色或蓝色等腰直角三角 形. 显然按此 E 作法可以得到无数个等腰直角三角形.(由本题也可以 证 明 上 一 题.)

B

C

例 5 设平面上给出了有限个点(不少于五点)的集 合 S, 其中若 干个点被染成红色,其余点被染成蓝色,且任意三个同色点不共线.求证:存在一个三角形, 具有下述性质: ⑴ 以 S 中的三个同色点为顶点; ⑵ 此三角形至少有一条边上不含另一种颜色的点. 分析 要证明存在同色三角形不难,而要满足第⑵个条件,可以用最小数原理. 证明 由于 S 中至少有五点,这些点染成两种颜色,故必存在三点同色.且据已知,此三 点不共线,故可连成三角形. 取所有同色三角形,由于 S 只有有限个点,从而能连出的同色三角形只有有限个,故其

中必有面积最小的.其中面积最小的三角形即为所求. 首先,这个三角形满足条件⑴,其次,若其三边上均有另一种颜色的点,则此三点必可 连出三角形,此连出三角形面积更小,矛盾. 说明 最小数原理,即极端原理.见第十二讲. 例 6 将平面上的每个点都染上红、蓝二色之一,证明:存在两个相似的三角形,其相似 比为 1995,且每一个三角形的三个顶点同色.(1995 年全国联赛加试题) 分析 把相似三角形特殊化, 变成证明相似的直角三角形, 在矩形的网格中去找相似的直角 三角形,这是证法 1 的思路.证法 2 则是研究形状更特殊的直角三角形:含一个角为 30?的直 角三角形.证明可以找到任意边长的这样的三角形, 于是对任意的相 似比, 本题均可证. 证法 3 则是考虑两个同心圆上三 条半径交圆得的 l R P S 三组对应点连出的两个三角形一定相似, 于是只要考 l 虑找同心圆上的 同色点, 而要得到 3 个同色点, 只要任取 5 个只染了 两种颜色的点就 T 行; 而要得到 5 个同色点, 则只要取 9 个只染了两种 l 颜色的点即行. Q 证明 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 三顶点同色(∠B 为 直角). 把△ABC D A 补成矩形 ABCD(如图).把矩形的每边都 分成 n 等分(n 为 正奇数,n>1,本题中取 n=1995).连结 对边相应分点, M 2 E' G E 把矩形 ABCD 分成 n 个小矩形. F N H F' AB 边上的分点共有 n+1 个,由于 n 为 奇数,故必存在 B C 其中两个相邻的分点同色,(否则任两个相 邻分点异色,则 P Q 可得 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 为圆心,2a 为半径作圆,若圆上有一个 红点, 则存在距 E F 离为 2a 的两个红点, 若圆上没有红点, 则任一圆内 接 六 边 形 ABCDEF 的六个顶点均为蓝色,但此六边形边长为 2a.故存在距 B 离为 2a 的两个蓝色点. A
1 2

下面证明:存在边长为 a, 3a,2a 的直角三 点同色.如上证,存在距离为 2a 的同色两点 A、

C

D

角形, 其三个顶 B(设为红点),

以 AB 为直径作圆,并取圆内接六边形 ACDBEF,若 C、D、E、F 中有任一点为红色,则存 在满足要求的红色三角形.若 C、D、E、F 为蓝色,则存在满足要求的蓝色三角形. 下面再证明本题:由上证知,存在边长为 a, 3a,2a 及 1995a,1995 3a,1995?2a 的两个同色三角形,满足要求. 证明 3 以任一点 O 为圆心,a 及 1995a 为半径作两个同心圆,在小圆上任取 9 点,其中 必有 5 点同色,设为 A、B、C、D、E,作射线 OA、OB、OC、OD、OE,交大圆于 A?,B?, C?,D?,E?,则此五点中必存在三点同色,设为 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的三角形,其三个顶点同为红色. 若圆上及圆内的点不全染成红色.则存在圆上或圆内一染成黄色的点 Q,|PQ|≤1.作△ PQR,使 PR=QR=2,则 R 必与 P、Q 之一染色不同.设 R 与 Q 染色不同,即 R 染红色. 2?取 QR 中点 M,则 M 必与 Q、R 之一同色.设与 R 同色,即同为 R S 红色. RM=1 为一边, 以 作正三角形△RMS、 △RMT. 若 S、 中任一点染 T T 红,则存在边长为 1 的红色顶点三角形.若 S、T 都为 黄色,则与 Q 组 M 成边长为 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 中部),比较两个只 形的两个 3?4 矩形,知,同色的 1?3 矩形的填法应 期出现的. 3?现考虑 1?12 矩形, 如图 果可知,图 2 中同色的 1?3 或 法相同.于是每个 1?12 矩形 矩形的填法相同.即图中一面 有 4 个 1?3 矩形,分别有 4 种 4?但 1?12 矩形中填了 5 某个 1?3 矩形中填了 2 个 2. 不 矩形中填了 2 个 2.于是用下 的染色法知每个 1?12 矩形中至少有 6 个 2. 由 3?、4?矛盾,知这样的填法不存在.

部分),由于它们 求的填法时, 它们 相错一个 1?3 矩 相同. 即染色是周
图1

图2

2,根据⑴的结 3?1 矩 形 的 填 应 与 一 个 3?4 的 1?12 矩形含 颜色. 个 2,从而必有 妨设黄色的 1?3 面的 1?12 矩形

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

习题 14
1.以任意方式对数轴上的每一坐标为整数的点染上红色或者蓝色.证明:对任意正整数 n ,都能找到无数个点,这些点同色且坐标能被 n 整除. 2.以任意方式对平面上的每一点染上红色或者蓝色.证明:一定可以找到无穷多个顶点 全为同一种颜色的三角形. 3.对正整数列按照以下方法由小到大进行染色:如果能够表示为两个合数的和,则染成 红色,否则染成蓝色.所有被染成红色的数中由小到大数的第 1994 个数是多少? 4.把一个马放入 4×8 的国际象棋棋盘的任何一格上,能否把它连跳 32 步,使得马跳遍 棋盘上每一格并回到最初位置? 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 届俄罗斯数学奥林匹克) 本节“情景再现”解答: 1.解 将(A)的方格染成黑白两色,使相邻的方格都不同色(图(C)),则此图中黑白方格的 个数相等,但如将⑴—⑺染色,则⑴—⑹都可染成黑白相间的两黑两白,但⑺只能染成一黑 三白或三黑一白,于是⑴—⑺染色后黑白方格数不等.所以(A)图不能被⑴—⑺完全覆盖. 而图(B)则因染色 后黑白格相差 1 格,故有被盖住的可 能.经试验,可如 (3) (7) 图(D)沿粗线分开的方 格分别用⑴—⑺盖 (4) (2) 住. (5) (6) 2.解 把 75×75 方格与图中给出的 (1) 4 种形状的小方格都 染成黑白两色,使 (C) (D) 任何相邻的格子染色 不同. 由于 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 的五边形有无穷多个,故由 抽屉原理知,至少有一种形状的(三个顶点同色的)三角形有无数个.取这种形状的顶点同色的 三角形集合,该集合有无穷多个元素.但这无数个三角形均全等,于是据抽屉原理,必有其 中一种颜色的顶点的三角形有无穷多个. 5.分析 当涂红格少于或等于 6 时,只要划去时,先划去涂有红格的 3 行,则余下的红格
[来源:学.科.网 Z.X.X.K]

至多还有 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 个点中必有? ?+1=3 个点同色.这三 3? ? 点不可能在同一条直线上,可连成一个三角形,过这三个点的半径与大圆的三个交点再连成 三角形,这两个三角形就满足要求. 7.证明 ⑴ 第一行中必有一种颜色有至少 10 个设为红,把它们换到前 10 列,下面 3 行 的前 10 列中,若有某一行有 2 个红格,则可得证.设每行至多有 1 个红格.于是至少有 7 列 中没有红色格.这个 3×7 矩形可证(可见《情景再现》第 3 题的证明). ⑵ 由于一列 4 格染成 3 色,必有某色至少染 2 格.每种颜色染 2 格的方案都各有 6 种, 故共有 18 种可能.在 19 列中,必有两列染两格的方法相同.故证. 8.证明 分别在 AB、BC、CA 上取点 D、E、F, 使 A 1 AD=BE=CF= AB.易证 DE⊥BC,EF⊥AC,FD⊥ 3 E、F 三点染成红、蓝两色,故必有两点同色,设 D、 色.则若 BC 上除点 E 外还有一点 K 染成红色,则 直角△DEK.若 BC 上除 E 外全染蓝色.则 AB 与 外有任一点染蓝,就出现蓝色三角形.如果 AB、AC 点.则△ADF 即为红色顶点三角形.
D F B C

AB.由于 D、 E 两点染成红 出现红色顶点 AC 上除点 D 上没有蓝色

E

K

“习题 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 行,把上下两行的格子称为外格,中间两行的格子称为内格.外格 与内格的格子数一样多. 一只国际象棋的马不能一步从外格跳到外格, 所以如果马从某一 格开始每格正好跳一次地跳遍棋盘, 并且最后回到 起点,它就不能从

内格跳到内格(否则内格就会比外格多)这就说明 ,马只能外格与内格交替地跳.现在把半 个国际象棋棋盘按右图所示染色.显然,马从外格跳到内格时是跳到同色的格子上去,而从 内格跳到外格时也是跳到同色的格子上.这样一来,按上述跳法,马就只在同色的格子之间 跳动,这就说明,马是不能从这半个棋盘上的任一格出发,跳遍棋盘上的所有格子并回到起 点处的.故这样的跳法是不存在的. 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)个,中心的绿点共有 k+h 个.若这 14 个点中,红绿各一半, 3 则得 1 (2y+4z+k+3h)+k+h=7.即(2y+4z+k+3h)+3k+3h=21,?2y+4z+4k+6h=21.这是不可能 3 的.故证. 8.证明 把圆旋转 2π 称为一次旋转,再把四个同心圆从内到外依次称为圆Ⅰ、Ⅱ、Ⅲ、 100

Ⅳ. 先 过圆心 O 任作一条射线 OX,把四个圆旋转,使每个圆都有一个分点在 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 次.故 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 全为绿色.矛盾.这说明上底面的 5 条棱同色. A1 A4 A2 同理,下底面的 5 棱也同色. A3 下面再证明, 上下底面 10 条棱颜色全同. 反设上 底面 5 条棱钱 红,下底面 5 条棱全绿.由上证,A1B1、A1B2 不能 全红,但也不能 B5 B4 B1 全绿,故必一红一绿,设 A1B1 红,则 A1B2 绿,同理 得,A1B3 红,A B3 B2 况.故得证. 1B4 绿,A1B5 红,此时,△A1B1B5 又出现上证情 11. 证明 对于 n=3 的情况, 显然此时只有惟一的三角形且没有对角线, 其三个顶点异色, 故满足要求. 设对于 n=2k-1,命题成立.对于 n=2k+1,取多边形的一个顶点 A,与 A 相邻的两个 顶点异色,若这样的顶点 A 不存在,即与每个顶点相邻的两个顶点都 同色,则可得此多边形 的每个顶点都同色. 连此异色的两个顶点,则把原多边形分成一个满足要求的三角形及一个凸 2k 边形.若此 凸 2k 边形存在一个顶点 B,其相邻的两个顶点异色,则再连此二顶点,又把这个 2k 边形分 成一个三角形及一个凸 2k-1 边形,其相邻顶点异色,于是命题成立,若此凸 2k 边形中不存 在满足上述要求(相邻两个顶点异色)的顶点,则此多边形的顶点只能是相间地染成两种颜 色.此时回到原凸 2k+1 边形,其顶点 A 与此两种颜色的顶点相邻,故它染了第三种颜色,把 A 与其余所有顶点连都对角线.则把这个凸 2k+1 边形分成了 2k-1 个三角形满足要求.故 n =2k+1 时命题也成立.综上可知,命题对于一切奇数个顶点的凸多边形成立,从而对 2003 边形成立. 2 12.解 设 4 种颜色为 A、B、C、D,计算同一行的“异色对”数,共有 C4?252=6?252 个“异色对” .所以各行共有 100?6?252 个“异色对” . 2 而每个“异色对”的两小格都在不同的列中,不同的“列对”数共有 C100对. 100?6?25 -1? 于是必有某个“列对”中有? +1=76 个异色对. 99?50 ? ? 现考虑这 2 列,76 行所成的 76?2 矩阵:其同行两格染色不同.且每列中染某一色的格子 至多 25 格.如果{A,B}与{C,D}出现在两行中,则已证;同样,若{A,C}与{B,D}出现在两 行中,或{A,D}与{B,C}出现在两行中,问题也解决.设此三种组合中,每种都至多出现其
2

中的一对.则这三种对子中只能出现:① {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 个”矛盾.故证.

某种颜色出现至少?

学科网

w。w-w*k&s%5¥u 学科网 w。w-w*k&s%5¥u


更多相关文档:

2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题

2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题_学科竞赛_高中教育_教育专区。第 14 讲 染色问题本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅...

2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题

如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题 隐藏>> 第14 ...

2012江苏省数学竞赛《提优教程》教案:第14讲平几问题选讲

2012江苏省数学竞赛《提优教程》教案:第14讲平几问题选讲_学科竞赛_高中教育_教育专区。第 16 讲 平几问题选讲 平面几何在高中竞赛和国际竞赛中占有重要的地位,...

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

2012江苏省数学竞赛《提优教程》教案:第05讲 子集_学科竞赛_高中教育_教育专区。第 5 讲 子集本讲内容有子集、子集的个数、集合的划分及子集的应用。 设 ...

思科数学【提优教程】江苏省2012高中数学竞赛 第14讲 染色问题教案

思科数学【提优教程江苏省2012高中数学竞赛 第14讲 染色问题教案_金融/投资_经管营销_专业资料。思科数学【提优教程江苏省2012高中数学竞赛讲义 高中数学培优第...

2012江苏省数学竞赛《提优教程》教案:第67讲_图论问题(一)

2012江苏省数学竞赛《提优教程》教案:第67讲_图论问题(一)_学科竞赛_高中教育...即至少有 20-18=2 个同色三角形. 存在只有 2 个同色三角形的二染色 K6,...

2012江苏省数学竞赛《提优教程》教案:第68讲_图论问题(二)

2012江苏省数学竞赛《提优教程》教案:第68讲_图论问题(二)_学科竞赛_高中教育...颜色染色,每条线段恰好染一种颜色.证明存在一个染色方案,使 G*染色后不含以 ...

2012江苏省数学竞赛《提优教程》教案:第11讲_三角问题选讲

2012江苏省数学竞赛《提优教程》教案:第11讲_三角问题选讲_学科竞赛_高中教育_...第十一讲 三角问题选讲 三角既是一个数学分支,同时也是一种数学方法. 三角函数...

2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖

2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖_学科竞赛_高中教育_教育专区...说明 数学归纳法是解决与 n 有关组合问题的常用手法, 数学归纳法使得 问题建立...

2012江苏省数学竞赛《提优教程》教案:第59讲 概率1

2012江苏省数学竞赛《提优教程》教案:第59讲 概率1_学科竞赛_高中教育_教育专区。第 19 讲 概率(一) 概率的一些术语及基本知识. 1.基本事件:一次试验(例如掷...
更多相关标签:
染色问题公式 | 奥数染色问题 | 排列组合染色问题 | 图的染色问题 | 染色问题 小奥 | 环形染色问题 | 染色 | 鸡兔同笼 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com