9512.net
甜梦文库
当前位置:首页 >> 金融/投资 >>

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


第 14 讲 染色问题
本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅助解题的手段,通过染 色,把研究对象分类标记,以便直观形象地解决问题,因此染色就是分类的思想的具体化, 例如染成两种颜色,就可以看成是奇偶分析的一种表现形式.染色,也是构造抽屉的一个重 要方法,利用染色分类,从而构造出抽屉,用抽屉原理来解题. A 类例题 例 1⑴ 有一个 6×6 的棋盘,剪去其左上角和右下角各一个小格(边长为 1)后,剩下的 图形能不能剪成 17 个 1×2 的小矩形? ⑵ 剪去国际象棋棋盘左上角 2×2 的正方形后,能不能用 15 个由四个格子组成的 L 形 完全覆盖?

例 1(!)

例 1(2)

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

证明 ⑴如 图,把 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 形 2 2 或盖住 3 红 1 蓝,或盖住 1 红 3 蓝,设前者有 p 个,后者有 q 个. 于是红格共盖住 3p+q 个即 p+q 为偶数,即有偶数个 L 形.设有 2k 个 L 形.于是 mn=2k ×4=8k.故证. 说明 奇偶分析与染色联合运用解决本题.
用心 爱心 专心 1

情景再现
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 ⑴ 以任意方式对平面上的每一点染上红色或者蓝色.证明:一定可以找到无穷多
用心 爱心 专心 2

个顶点为为同一种颜色的等腰三角形. ⑵ 以任意方式对平面上的每一点染上红色或者蓝色.证明:一定可以找到无穷多个顶 点为为同一种颜色的等腰直角三角形. 分析 ⑴同样可以设置两难命题:由于等腰三角形的顶点在底边的垂直平分线上,故先 选两个同色点连成底边,再在连线的垂直平分线上找同色的点,这是解法 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 只有有限个点,从而能连出的同色三角形只有有限个,故 其中必有面积最小的.其中面积最小的三角形即为所求. 首先,这个三角形满足条件⑴,其次,若其三边上均有另一种颜色的点,则此三点必 可连出三角形,此连出三角形面积更小,矛盾.
用心 爱心 专心 3

说明 最小数原理,即极端原理.见第十二讲. 例 6 将平面上的每个点都染上红、蓝二色之一,证明:存在两个相似的三角形,其相 似比为 1995,且每一个三角形的三个顶点同色.(1995 年全国联赛加试题) 分析 把相似三角形特殊化, 变成证明相似的直角三角形, 在矩形的网格中去找相似的直 角三角形,这是证法 1 的思路.证法 2 则是研究形状更特殊的直角三角形:含一个角为 30? 的直角三角形. 证明可以找到任意边长的这样的三角 形,于是对任 意的相似比,本题均可证.证法 3 则是考虑两个同心 圆上三条半径 l S R P 交圆得的三组对应点连出的两个三角形一定相似, 于 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 为 直角).把△ D A ABC 补成矩形 ABCD(如图).把矩形的每边 都分成 n 等分 (n 为正奇数,n>1,本题中取 n=1995).连 结对边相应分 2 M 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、 B( 设 为 红 C D 点), 以 AB 为直径作圆, 并取圆内接六边形 ACDBEF, 若 C、D、E、 F 中有任一点为红色,则存在满足要求的红色三角形.若 C、D、E、F 为蓝色,则存在满足
用心 爱心 专心 4

要求的蓝色三角形. 下面再证明本题:由上证知,存在边长为 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 矩形, 若存在满足要 求的填法时, 它
用心 爱心 专心
图1

5



们的填法必相同. 2?对于任一 3?n 矩形(如图 2 中部), 比较两个只相错一个 1?3 矩形的两个 3?4 矩形, 知, 同色的 1?3 矩形的填法应相同.即染色是周期出现的. 3?现考虑 1?12 矩形,如图 2,根据⑴的结果可知,图 2 中同色的 1?3 或 3?1 矩形的填 法相同. 于是每个 1?12 矩形应 与一个 3?4 矩 形的填法相同.即图中一面的 1?12 矩 形含 有 4 个 1?3 矩形,分别有 4 种 颜色. 4?但 1?12 矩形中填了 5 个 2 ,从而必有 某个 1?3 矩形中填了 2 个 2. 不 妨设黄色的 1?3 矩形中填了 2 个 2. 于是用 下 面 的 1?12 图2 矩形的染色法知每个 1?12 矩 形中至少有 6 个 2. 由 3?、4?矛盾,知这样的填法不存在.

情景再现
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 内部取若干点也任 意涂红、黑、兰三色之一,这些点间(没有三点共线)连有一 些线段,把大三角形分成若干 互相没有重叠部分的一些小三角形.求证:不论怎样涂, 都有一个小三角形, 其三个顶点涂的 颜色全不同.
用心 爱心 专心 6

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 行,则余下的红 格至多还有 3 格,再划去有涂红格的列(当然不超过 3 列)则所有的涂红格都被划去了. 仿此,当涂红格少于或等于 9 格时,由于这个图形 只有 6 行, 故总有 某些行的涂红格不止 1 格, 首先划去涂红格至少 2 格的 某一行, 余下 5 行 中,如涂红的格子仍不止 5 格,则必有某行的不止 1 个 涂红格, 再划去至 少有 2 个涂红格的行,从第二步起,如涂红格不足 3 格 时, 则任意划去某 行.这样,当涂红格不多于 9 格时,总可以划去 3 行, 使余下涂红格不
用心 爱心 专心 7

多于 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×7 矩形可证(可见《情景再现》第 3 题的证明). ⑵ 由于一列 4 格染成 3 色,必有某色至少染 2 格.每种颜色染 2 格的方案都各有 6 种, 故共有 18 种可能.在 19 列中,必有两列染两格的方法相同.故证. 1 8. 证明 分别在 AB、 BC、 CA 上取点 D、 E、 F, 使 AD=BE=CF= AB. 易 3 证 DE⊥BC,EF⊥AC,FD⊥AB.由于 D、E、F 三点染成红、蓝两色, 故必有两点同色,设 D、E 两点染成红色.则若 BC 上除点 E 外还有 一点 K 染成红色,则出现红色顶点直角△DEK.若 BC 上除 E 外全染 蓝色. 则 AB 与 AC 上除点 D 外有任一点染蓝, 就出现蓝色三角形. 如 果 AB、AC 上没有蓝色点.则△ADF 即为红色顶点三角形.
D F B C A

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
用心 爱心 专心 8

白 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 的.故证. 2π 8.证明 把圆旋转 称为一次旋转,再把四个同心圆从内到外依次称为圆Ⅰ、Ⅱ、Ⅲ、 100 Ⅳ. 先过圆心 O 任作一条射线 OX,把四个圆旋转,使每个圆都有一个分点在 OX 上,固定圆 Ⅰ,其上的某个分点 A 在 OX 上,旋转圆Ⅱ,使其上每个点都与 OX 对齐一次,记下圆Ⅱ在每 个位置时两圆同色点对齐的点对个数,由于圆Ⅱ的每个点都与圆Ⅰ的点 A 对齐 1 次,故点 A 在旋转过程中共与圆Ⅱ的同色点对齐了 50 次,每个圆Ⅰ的点都是这样,故在圆Ⅱ的旋转过 程中, 共有 50?100 次同色点对齐. 于是至少有一次, 同色点对齐的点对数不少于? ? 50?100? ?= ? 100 ?

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

同样,把圆Ⅳ与圆Ⅲ的同色点对齐个数最多的位置固定,此时圆Ⅳ与圆Ⅲ至少有? ?

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

解法 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 1B4 B3 B2 绿,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?25 =6?25 12.解 设 4 种颜色为 A、B、C、D,计算同一行的“异色对”数,共有 C4
2 2

个“异色对” .所以各行共有 100?6?25 个“异色对” .
2

而每个“异色对”的两小格都在不同的列中,不同的“列对”数共有 C2 100对. 于是必有某个“列对”中有? ? 100?6?25 -1? ?+1=76 个异色对. ? 99?50 ?
2

现考虑这 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

用心 爱心 专心

10

的个数有? ?

76-1? ?+1=38 个,第二种情况,由于只出现 A、B、C 三种颜色,故任一列中总有 ? 2 ? 76-1? ?+1=26 个,均与“每列中同色方格不超过 25 个”矛盾.故证. ? 3 ?

某种颜色出现至少? ?

用心 爱心 专心

11



更多相关文章:
思科数学【提优教程】江苏省2012高中数学竞赛 第13讲 ...
思科数学【提优教程】江苏省2012高中数学竞赛 第13讲 奇偶分析教案_金融/投资_...奇偶分析也常表现为染色,把一个图形染成黑白两色,往往可视为其中一色为奇数, ...
思科数学【提优教程】江苏省2012高中数学竞赛 第09讲 ...
思科数学【提优教程】江苏省2012高中数学竞赛 第09讲 函数性质的应用(最终)教案 思科数学【提优教程】江苏省2012高中数学竞赛讲义 高中数学培优思科数学【提优教程】...
思科数学【提优教程】江苏省2012高中数学竞赛 第04讲 ...
思科数学【提优教程】江苏省2012高中数学竞赛 第04讲 集合的概念与运算教案_金融/投资_经管营销_专业资料。思科数学【提优教程】江苏省2012高中数学竞赛讲义 高中...
2012江苏省数学竞赛提优教程教案:第14讲 染色问题
2012江苏省数学竞赛提优教程教案:第14讲 染色问题_学科竞赛_高中教育_教育专区。第 14 讲 染色问题本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅...
思科数学【提优教程】江苏省2012高中数学竞赛 第11讲 ...
思科数学【提优教程】江苏省2012高中数学竞赛 第11讲 极端原理教案 思科数学【提优教程】江苏省2012高中数学竞赛讲义 高中数学培优思科数学【提优教程】江苏省2012高...
...江苏省数学竞赛提优教程教案:第14讲 染色问题_...
高一英语上册unit1教案1/2 相关文档推荐 思科数学【提优教程】江苏... 11页 ...2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题 隐藏>> 第14 讲 染色...
思科数学【提优教程】江苏省2012高中数学竞赛 第02讲 ...
思科数学【提优教程】江苏省2012高中数学竞赛 第02讲 二次函数与二次不等式教案 思科数学【提优教程】江苏省2012高中数学竞赛讲义 高中数学培优思科数学【提优教程...
2012江苏省数学竞赛提优教程教案:第05讲 子集
2012江苏省数学竞赛提优教程教案:第05讲 子集_学科竞赛_高中教育_教育专区。第 5 讲 子集本讲内容有子集、子集的个数、集合的划分及子集的应用。 设 ...
2012江苏省数学竞赛提优教程教案:第60讲 概率2
2012江苏省数学竞赛提优教程教案:第60讲 概率2_学科竞赛_高中教育_教育专区...求解等基础知识,考查通过建立简单的数学模型以解决实际问题的能力. 解(1) P ...
2012江苏省数学竞赛提优教程教案:第10讲 抽屉原理
2012江苏省数学竞赛《提优教程》教案:第10讲 抽屉原理...抽屉原理常常结合几何、整除、数列和染色问题出现,...思科数学【提优教程】江... 10页 1下载券 2012...
更多相关标签:

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

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