染色问题与染色方法
巡山小妖精
666次浏览
2021年01月22日 15:26
最佳经验
本文由作者推荐
-关于水浒传的歇后语
染色问题与染色方法
1
．
小方格染色问题
最简单的染色问题是从一种民间游戏中发展起来的方格盘上的染色问 题
.
解决这类问题的方
法后来又发展成为解决方格盘铺盖问题的重要技巧
.
例
1
如图
29-1(a),3
行
7
列小方格每一 个染上红色或蓝色
.
试证
:
存在一个矩形
,
它的四个角上< br>的小方格颜色相同
.
证明
由抽屉原则
,第
1
行的
7
个小方格至少有
4
个不同色
,不妨设为红色
(
带阴影
)
并在
1
、
2
、
3
、
4
列（如图
29-1
（
b
））.
在第
1
、
2
、
3
、
4
列 （以下不必再考虑第
5
，
6
，
7
列）中，如第
2< br>行或第
3
行出现两个红色
小方格，
则这个问题已经得证；
如第
2
行和第
3
行每行最多只有一个红色小方格
（如图
29-1
（
c
）），那么在这两行中必出现四角同为蓝色的矩形，问题也得到证明
.
说明：（
1
）在上面证明过程中除了运用抽屉原则外，还要用到一种思考问题的有效方 法，
就是逐步缩小所要讨论的对象的范围，把复杂问题逐步化为简单问题进行处理的方法
. < br>（
2
）此例的行和列都不能再减少了
.
显然只有
两行的方格盘 染两色后是不一定存在顶点同
色的矩形的
.
下面我们举出一个
3
行< br>6
列染两
色不存在顶点同色矩形的例子如图
29-2.
这说
明
3
行
7
列是染两色存在顶点同色的矩形的最
小方格盘了
.< br>至今
,
染
k
色而存在顶点同色的矩
形的最小方格盘是什么还不 得而知
.
例
2 (
第
2
届全国部分省市初中数学通讯赛 题
)
证明
:
用
15
块大小是
4×
1
的矩形瓷砖和
1
块大
小是
2×
2
的矩形瓷砖，
不 能恰好铺盖
8×
8
矩形
的地面
.
分析
将
8×
8
矩形地面的一半染上一种颜色，
另一半染上另一种颜色，< br>再用
4×
1
和
2×
2
的矩
形瓷砖去盖，如果盖住的两种颜色的小矩形不是一样多，
则说明在给定条件不完满铺盖不可
能
.
证明
如图
29-3
，
用间隔为两格且与副对角线平行的 斜格同色的染色方式，
以黑白两种颜色
将整个地面的方格染色
.
显然，地面上 黑、白格各有
32
个
.
每块
4×
1
的矩形砖不论 是横放还是竖盖，且不论盖在何处，总是占据地面上的两个白格、
两个黑格，
故
15< br>块
4×
1
的矩形砖铺盖后还剩两个黑格和两个白格
.
但由于与 副对角线平行的
斜格总是同色，而与主对角线平行的相邻格总是异色，所以，不论怎样放置，一块
2×
2
的
矩形砖，总是盖住三黑一白或一黑三白
.
这说明剩下的一 块
2×
2
矩形砖无论如何盖不住剩下
的二黑二白的地面
.
从 而问题得证
.
例
3
（
1986
年北京初 二数学竞赛题）如图
29-4
（
1
）是
4
个
1×< br>1
的正方形组成的
“L”
形，用
若干个这种
“L”
形 硬纸片无重迭拼成一个
m×
n
（长为
m
个单
位，宽为
n
个单位）的矩形如图
29-4
（
2
）
.
试证明
mn
必是
8
的倍数
.
证明∵
m×
n矩形由
“L”
形拼成，∴
m×
n
是
4
的倍数， ∴
m
、
n
中必有一个是偶数，
不妨设为
m.
把m×
n
矩形中的
m
列按一
列黑、一列白间隔染色（如图
29-4
（
2
）），则不论
“L”
形在
这矩形中的放置位置 如何（
“L”
形的放置，共有
8
种可能），
“L”
形或占有
3
白一黑四个单位正方形（第一种），或占有
3
黑一白四个单位正方形（第二 种）
.
设第一种
“L”
形共有
p
个，
第二种“L”
形共
q
个，
则
m×
n
矩形中的白格单位 正方形数为
3p+q
，
而它的黑格单位正方形数为
p+3q.
∵< br>m
为偶数，
∴
m×
n
矩形中黑、
白条数相同，
黑、
白单位正方形总数也必相等
.
故有
3p+q=p+3q
，从而
p=q.
所以
“L”
形的总数为
2p
个，即
“L”
形总数为偶数，所以
m×
n
一定是
8
的倍数
.
2
．
线段染色和点染色
下面介绍两类重要的染色问题
.
(1)
线段染色
.
较常见的一类染色问题
是发样子组合数学中图论知识的所谓
“
边染色
”（或称
“
线段染色
”
），主要借
助抽屉原则求解
.
例
4
（
1947
年匈牙利数学奥林匹克
试题）世界上任何六个人中，一定有
3
个人或者互相认识或者互相都不认识
.
我们不直接证明这个命题，而来看与之等价的下述命题
例
5 < br>（
1953
年美国普特南数学竞赛题）空间六点，任三点不共线，任四点不共面，成对地
连接它们得十五条线段，用红色或蓝色染这些线段（一条线段只染一种颜色）
.
求证< br>:
无论怎
样染
,
总存在同色三角形
.
证明
设
A
、
B
、
C
、
D
、
E
、
F
是所给六点
.
考虑以
A
为端点的线段
AB
、
AC
、
AD
、
AE
、
AF
，
由抽屉原则这五条线段中至少有三条颜色相同，不妨设就是
AB
、
AC、
AD
，且它们都染成
红色
.
再来看
△
BCD
的三边，如其中有一条边例如
BC
是红色的，则同色三角形已出现（红
色△
ABC
）；如
△
BCD
三边都不是红色的，则它就是蓝色的三 角形，同色三角形也现了
.
总
之
,
不论在哪种情况下
,都存在同色三角形
.
如果将例
4
中的六个人看成例
5
中六点
,
两人认识的连红线
,
不认识的连蓝线
,
则例
4
就变成了
例
5.
例
5
的证明实际上用染色方法给出了例
4
的证明
.
例
6 (
第
6
届国际数学 奥林匹克试题
)
有
17
位科学家
,
其中每
一个人和 其他所有人的人通信
,
他们的通信中只讨论三个题
目
.
求证
:
至少有三个科学家相互之间讨论同一个题目
.
证明
用平面上 无三点共线的
17
个点
A
1
,A
2
,…
，
A
17
分别表
示
17
位科学家
.
设他们讨 论的题目为
x,y,z,
两位科学家讨论
x
连红线
,
讨论< br>y
连蓝线
,
讨论
z
连黄线
.
于是只须证明以 这
17
个点为顶点的三角形中有一同色三角形
.
考虑以
A
1
为端点的线段
A
1
A
2
,A
1
A
3
,…
，
A
1
A
17
，由抽屉原则
这< br>16
条线段中至少有
6
条同色，不妨设
A
1
A
2
，
A
1
A
3
，
…
，
A
1
A
7
为红色
.
现考查连结六点
A
2
，
A
3
，
…
，
A
7
的
15
条线段，如其中至少有一条红色线段，
则同色（红色）三角形已出现；如没有红色线段，则这
1 5
条线段只有蓝色和黄色，由例
5
知一定存在以这
15
条线段中某三 条为边的同色三角形（蓝色或黄色）
.
问题得证
.
上述三例同属图论中的接 姆赛问题
.
在图论中
,
将
n
点中每两点都用线段相连所得的 图形叫做
n
点完全图
,
记作
k
n
.
这些点 叫做
“
顶点
”
，这些线段叫做
“
边
”.
现 在我们分别用图论的语言来叙
述例
5
、例
6.
定理
1
若在
k
6
中，任染红、蓝两色，则必有一只同色三角形
.
定理
2
在
k
17
中
,
任染红、蓝、黄 三角，则必有一只同色三角形
.
（
2
）点染色
.
先看离散的有限个点的情况
.
例
7
（首届全国中学生数学冬令营试题）能否把
1
，
1< br>，
2
，
2
，
3
，
3
，
…< br>，
1986
，
1986
这些
数排成一行，使得两个
1
之间夹着一个数，两个
2
之间夹着两个数，
…
，两个
198 6
、之间
夹着一千九百八十六个数？请证明你的结论
.
证明
< br>将
1986×
2
个位置按奇数位着白色，偶数位着黑色染色，于是黑白点各有< br>1986
个
.