29涂色问题
涂色问题是数学竞赛中较为典型的问题，可以直接用抽屉原则解决涂色问题。另一方面，也可以将别的有关问题“涂色”，转化为涂色问题，涂色问题本身，有其深刻的数学背景。有些问题，本来就属于图论的内容。有些问题的解决，则需要用到数论、组合数学的理论和方法。这里介绍，只是中学数学竞赛中的有关问题。
1． 小方格染色问题
最简单的染色问题是从一种民间游戏中发展起来的方格盘上的染色问题.解决这类问题的方法后来又发展成为解决方格盘铺盖问题的重要技巧. 2． 线段染色和点染色
(1)线段染色.较常见的一类染色问题是发样子组合数学中图论知识的所谓“边染色”（或称“线段染色”），主要借助抽屉原则求解.
（2）点染色.先看离散的有限个点的情况.
例题讲解
1．把正方形ABCD的一边AB分成n段，使奇数号的线段长度之和等于偶数号的线段长度之和（如图01—01）。过各分点作平行于AD的线段，得到n个矩形。每一个矩形又被对角线BD分成两部分。将奇数号矩形左部及偶数号矩形的右部涂上同一颜色。证明：在对角线BD两侧的有同色的部分，其面积和相等。
2．在一张无限方格纸的某些方格上涂上红色，其余方格涂上蓝色，每一个2×3的六方格矩形内恰好2个红方格。试问：一个9×11的99方格矩形内包含多少个红方格？
3．在n×n（n≥2）个方格的正方形表中，有n－1个格子里涂了色，求证：通过交换
两行或两列的位置，总可以将所有涂色的方格移到正方形表的左上角顶点到右下角顶点的对角线下方。
4．有n×n（n≥3）个方格表中，先在表中任意选出n－1个方格都涂成黑色，然后将那些凡是至少与两个已涂色的方格相邻的方格也都涂黑色。求证：不论怎样选择最初的n－1个方格，都不能按这样的法则，将表中的所有方格全涂黑。
5．设ABC为正三角形，E为线段BC，CA，AB上点的集合（包括A，B，C在内）。将E分成两个子集，求证：总有一个子集中含有一个直角三角形的顶点。
6．设a1，a2，a3……是一个不减的正整数序列，定义bm是使an≥m的n的最小值，若a19=85，试求a1+a2+…+a19+b1+b2+…+b85的值。
7．有1987块玻璃片，每块上涂有红、黄、蓝三色之一，进行下列操作：将不同颜色的两块玻璃片擦净，然后涂上第三种颜色。
（1）求证：无论开始时红、黄、蓝色玻璃片各有多少块，总可以经过有限次操作而使所有的玻璃片涂有同一种颜色；
（2）求证：玻璃片最后变成哪种颜色，与操作顺序无关。
8．把集合M={1，2，…，1987}的元素用4种颜色涂色，求证：至少存在一种涂色方法，使得M中任何等差数列的10项，不是同一颜色。
9．平面直角坐标系中，纵横坐标都是整数的点称为整点称为整点。设计一种方法，将所有整点涂色，每一个整点染成白色、红色或黑色中的一种颜色，使得 （1）每一种颜色的点出现在无穷多条平行于横轴的直线上；
（2）对任意白点A、红点B及黑点C，总可以找到一个红点D，使得ABCD为一平行四边形。证明你设计的的方法符合上述要求。
10．将平面上每个点染上两种颜色中的一种，已知任一边长为1的正三角形都有两种颜色的顶点，
（1）求证：存在边长为3的同色正三形（即顶点同色）； （2）举出染色满足题设要求的平面的例子。
11．平面上有6点，任何三点都是一个不等边三角形的顶点，求证：这些三角形的边中一定有一条，它在一个三角形中是最长边，而在另一个三角形中是最短边。
12．平面上任一点都染上红、蓝、黄三色中的一种，求证：一定存在一条端点同色且长度为1的线段。
课后练习
高中数学竞赛专题精讲29涂色问题(含答案)
