文档内容
NEW(cid:0)(cid:0)HOPE(cid:0)(cid:0)CUP
★"#★
第十七讲 染色问题
暋
1 染色问题
.
染色是分类的直观表现 在数学竞赛中有很多以染色为背景的问题 这类问
, ,
题的特点是知识点少 逻辑性强 技巧性强 其内部蕴藏着深刻的数学思想
, , , 。
解答染色问题 并不需要具备很多的数学知识 只需要具有缜密的思考能力
, ,
和较强的分析能力 解决染色问题常用的方法有以下几种 奇偶分析 归纳法 抽
。 : 、 、
屉原理 构造法 组合计数等
、 、 。
2 染色方法
.
像国际象棋的棋盘那样 将问题中的对象适当进行染色 有利于观察 分析对
, , 、
象之间的关系 我们可以把被研究的对象染上不同的颜色 许多隐藏的关系会变
, ,
得明了 再通过对染色图形的处理达到对原问题的解决 这种解题方法称为染色
, ,
法 常见的染色方式有 点染色 线段染色 小方格染色和区域染色
。 : 、 、 。
经 典 范 例
例1 教室里有 排椅子 每排 张 每张椅子上坐一个学生 如果一周
暋 5 , 5 , 。
后 每个学生都必须与和他相邻 前 后 左 右 的某一个同学交换座位 能不能换
, ( 、 、 、 ) ,
成 为什么
? ?
点 拨 将 个座位相间染色 再利用奇偶性进行分析
暋 25 , 。
详 解 如图 将 个座位相间染色
暋 , 25 :
130 www.newhopecup.com
暋暋暋暋 暋暋暋暋暋暋" #
$
!
按照题目规定交换座位 就是将黑格与白格全部进行交换
, ,
但黑格有 个 白格有 个 黑格比白格多一个
13 , 12 , , 其
这就是说 这种交换总有 人办不到 因此不能换成 曲
, 1 , 。 弥
小 结 解决染色问题常采用奇偶性进行分析,最后得出结论。 高
暋 氋 其
和
弥
寡
例2 中国象棋盘的任意位置上有一只马 它跳了若干步正好回到原来 氌
暋 , 氞
宋
玉
的位置 马所跳的步数是偶数还是奇数 为什么 氠
。 ? ?
点 拨 马走 斜日 我们首先将棋盘上的各点按黑白色间隔染色之后再分
暋 “ 暠,
类分析
。
详 解 把棋盘上各点按黑白色间隔染色 如下图
暋 , :
如果马从黑点出发 第一步只能跳到白点 马走 斜日 第二步再从白点跳
, ( “ 暠),
到黑点 因此马从起点位置相继经过 白 黑 白 黑 要想回到黑点必须白 黑
。 : 、 、 、 、… 、
成对 即跳偶数步
, 。
同理 如果马从白点出发 要想回到白点也必须跳偶数步
, , 。
由此可见 马所跳的步数是偶数步
, 。
小 结 最常见的染色方法就是相间染色。
暋
例3 正方形的展览会场地被分割成 间相同的正方形房间 每个房间
暋 16 ,
都有门通向隔壁房间 如左图 现在安排入口在右下角 出口在左上角 能不能
( )。 , 。
使参观的人不重复地走完所有房间
?
点 拨 将 个房间相间染色
暋 16 。
www.newhopecup.com 131
暋暋暋暋暋暋暋暋 暋暋NEW(cid:0)(cid:0)HOPE(cid:0)(cid:0)CUP
★"#★
详 解 我们把 间房间如图黑白相间染色
暋 16 ,
因为入口是黑格 接着进入的必定是白格 随后又从白格进入黑格
, , ,
房间一共 间 其中黑格和白格各 个
16 , 8 ,
由于黑 白格的房间数相等 线路又是黑白相间
、 , ,
所以出口处应是白格 但现在的出口处是黑格
, ,
因此不能使参观的人不重复地走完所有房间
。
小 结 染色方法是对题目所研究的对象进行分类的一种形象化的方法。利
暋
用染色的方法能解决很多问题。
例4 一批现成的木箱 尺寸是 现有一批商品 每件都是长方
暋 , 6暳6暳6, ,
体形状 它们的尺寸是 能不能用这样的商品将木箱填满
, 1暳2暳4, ?
点 拨 如果用 来算 说正好装 件商品 那就错
暋 6暳6暳6暵(1暳2暳4)=27 , 27 ,
了 事实上这 件商品是无法全部装入木箱的 原因在哪里呢 通过染色法可
。 27 , ?
找出原因
。
详 解 将 的木箱分成 个 的单位正方体 每 个单位
暋 6暳6暳6 216 1暳1暳1 , 8
正方体可组成一个 的正方体 整个正方体一共有 个这种正方体 我们
2暳2暳2 , 27 。
相间地将其染成黑 白两色 其中 个染成黑色 个染成白色 这样 一共有
、 , 14 ,13 。 , 8
个黑色单位正方体 个白色单位正方体
暳14=112 ,8暳13=104 。
把 的商品放入木箱 每件商品必须填充 个单位正方体 其中黑色和
1暳2暳4 , 8 ,
白色的都是 个 保持相等的关系 但由于 所以商品不能填满木箱
4 , 。 112曎104, 。
小 结 染色的方法往往取决于“格子暠的形状,其在空间的位置特征决定了
暋
方法的特殊性。
例5 有一个 的方格图形 将其中一些方格染成黑色 然后任意划
暋 4暳4 , ,
去两行 两列方格 如果要求剩下的方格里至少还有一个黑格 那么至少要将几
、 。 ,
132 www.newhopecup.com
暋暋暋暋 暋暋暋暋暋暋" #
$
!
个方格染成黑色
?
点 拨 先画图说明只染 个方格是可以的 再证明少于 个不行
暋 7 , 7 。 略
翻
详 解 如图 将图形中的 个小方格染成黑色
书
暋 , 7 ,
数
则
氋
便
不
愧
三
餐
氌
氞
陈
字
自
氠
不论划去哪两行和两列 都至少剩下一个黑格
, 。
下面证明 将任意 个小方格染成黑色 总可以划去两行和两列 使得没有黑
: 6 , ,
格剩下
。
若任意两行含有最多 个黑格 黑格总数最多 个 矛盾
3 , 2+1暳3=5 , ,
所以存在两行含有至少 个黑格 将这两行划掉
4 , ,
剩下的两个黑格可通过两列划掉
。
答 至少要将 个方格染成黑色 才能满足题目条件
: 7 , 。
小 结 画出符合题意的图后,我们还要证明比染 个更少的都不符合题意,
暋 7
这样才能得出至少要将 个方格染黑的结论。
7
例6 将正方体的六个面涂上颜色 每个面涂红 黄 蓝色中的一种 正方
暋 , 、 、 ,
体有些顶点是三个颜色不同的面的交点 这样的顶点最多有多少个 再把每一个
。 ?
这样的顶点都装上红 黄 蓝三色灯泡之一 问 至少有几个灯泡的颜色是相同的
、 、 , : ?
点 拨 要使由三种颜色都不同的面的交点形成的顶点尽可能多 只要把正
暋 ,
方体的三对相对的两个面分别涂成红色 黄色或蓝色即可
、 。
详 解 只要把正方体的三对相对的两个面分别涂成红色 黄色或蓝色 那么
暋 、 ,
每个顶点的三个面就互不相同了 即正方体的 个顶点都符合题目要求
, 8 。
根据抽屉原理 至少有 个灯泡的颜色是相同的
8暵3=2……2, , 3 。
小 结 染色问题中经常用到抽屉原理,同时利用染色也是制造抽屉的常用
暋
方法。
例7 图 是 个 的正方形组成的 形 用若干个这种 形硬
暋 1 4 1暳1 “L暠 , “L暠
纸片无重叠地拼成一个m n长为m个单位 宽为n个单位 的矩形 如图 试
暳 ( , ) , 2。
www.newhopecup.com 133
暋暋暋暋暋暋暋暋 暋暋NEW(cid:0)(cid:0)HOPE(cid:0)(cid:0)CUP
★"#★
证明mn必是 的倍数
8 。
点 拨 这个m n的矩形是用若干个 L 形硬纸片无重叠拼成的 即可说明
暋 暳 “暠 ,
mn必是 的倍数 再通过染色来证明mn必是 的倍数
4 , 8 。
详 解 易知m n是 的倍数 mn中必有一个是偶数 不妨设为m
暋 暳 4 ,曕 、 , ,
把m n矩形中的m列按一列黑 一列白间隔染色 如图
暳 、 ( 2),
则不论 形在这矩形中的放置位置如何 形的放置 共有 种可能
“L暠 (“L暠 , 8 ),“L暠
形或占有 白 黑四个单位正方形 第一种 或占有 黑 白四个单位正方形 第
3 1 ( ), 3 1 (
二种
)。
设第一种 形共有p个 第二种 形共有q个 则m n矩形中的白格单
“L暠 , “L暠 , 暳
位正方形数为 p q而它的黑格单位正方形数为p q
3 + , +3 。
m为偶数 m n矩形中黑 白条数相同 黑 白单位正方形总数也必相
曔 ,曕 暳 、 , 、
等
。
故有 p q p q从而p q
3 + = +3 , = 。
形的总数为 p个 即 形总数为偶数
曕“L暠 2 , “L暠 ,
所以m n一定是 的倍数
暳 8 。
小 结 直接证明mn是 的倍数不好证,所以我们先证mn是 的倍数,由
暋 8 2
此得出mn中必有一个是偶数,再进一步证明mn是 的倍数。
8
挑 战 自 我
.音乐教室里有 排椅子 每排 把 每把椅子上坐着一个学生 老师每月都
1 7 , 7 , 。
要将座位调换一次 张明同学向老师建议 每个同学都必须与他相邻 前 后 左
, , ( 、 、 、
右 的某一个同学交换座位 老师告诉他 这样交换座位不可能做到 你知道为
) 。 , 。
什么吗
?
134 www.newhopecup.com
暋暋暋暋 暋暋暋暋暋暋" #
$
!
.用三种颜色对下图进行染色 能不能使得相邻的区域颜色不同
2 , ?
读
书
如
行
路
氋
历
险
毋
惶
恐
.一个 马 放在 的棋盘上 它接连跳 次 能否跳遍棋盘上每一格并且 氌
3 “ 暠 5暳5 , 25 , 氞
氭
回到初始位置 清
? 诗
铎
·
读
书
氱
氠
.有一个 的棋盘方格 请将每一个方格染成黑色或白色 使得每行每列
4 8暳8 , ,
都有恰好 个方格同色 并且黑 白方格的总数都是 个
6 , 、 32 。
.证明 用 块大小是 的矩形瓷砖和 块大小是 的矩形瓷砖 不
5 : 15 4暳1 1 2暳2 ,
能恰好铺盖 矩形的地面
8暳8 。
. 的国际象棋棋盘能不能被剪成 个 的正方形和 个 的长
68暳8 7 2暳2 9 4暳1
方形 如果可以 请给出一种剪法 如果不行 请说明理由
? , ; , 。
.如下图 把正方体分割成 个相等的小正方体 在中心的那个小正方体中
7 , 27 ,
有一只甲虫 甲虫能从每个小正方体爬到与这个正方体相邻的 个小正方体 那
, 6 。
么甲虫能不重复地走遍所有的正方体吗
?
www.newhopecup.com 135
暋暋暋暋暋暋暋暋 暋暋NEW(cid:0)(cid:0)HOPE(cid:0)(cid:0)CUP
★"#★
.平面上nn 个点A A A A 顺次排在同一条直线上 每点涂上黑
暋暋8 (曒2) 1、2、3、… n ,
白两色中的某一种颜色 已知A 和A 涂上的颜色不同 证明 相邻两点间连接
。 1 n 。 :
的线段中 其两端点不同色的线段必为奇数条
, 。
.用黑 白两种颜色将一个 的长方形中的小方格随意染色 求证 在这
9 、 5暳5 。 :
个长方形中一定有一个由小方格组成的长方形 它的四个角上的小方格同色
, 。
.能否用下图中各种形状的纸片 不能剪开 拼成一个边长为 的正方形
10 ( ) 99
图中每个小方格的边长为 请说明理由
( 1)? 。
.如图由 块 的正方形拼成 你能否用 块 的长方形将图形盖
11 18 1暳1 , 9 2暳1
住
。
.能否把 这些数排成一行 使得两个 之间夹
12 1,1,2,2,3,3,…,1986,1986 , 1
着 个数 两个 之间夹着 个数 两个 之间夹着 个数 请证明你
1 , 2 2 ,…, 1986 1986 ?
的结论
。
136 www.newhopecup.com
暋暋暋暋 暋暋暋暋暋暋
