染色问题

高中数学竞赛讲座二试内容19

染色问题 （一）

一．基本方法

染色问题的本质是对集合的元素进行分类的问题，染色可以使分类更直观、更形象．

染色问题主要有两类：一类使借助染色方法解决问题；二类是问题的条件是用染色的方式给出的．常

见的染色问题有对区域的染色（包括对方格，三角形的染色），对线段的染色，对点的染色．常用思想方法是整体思想，抽屉原理，考虑极端情形，数学归纳法，构造思想等． 二．例题精选

（一）．k染色平面问题

将平面上的点用不超过k种颜色给每一个点染一种颜色，这样的平面叫做k染色平面．

１．坐标平面上若干个整点，将一些整点染红色，一些染蓝色，证明：总可以有一种染法使每行、每列两

种颜色点数之差不超过１．

R B R R B B R B B R B R B R R B R B R B

R B R B R

B R B R B

２．对于任意的a>0，二染色平面上必存在斜边长为a且内角分别为30?,60?,90?的三顶点同色的三角形．

B B

Ｒ a Ｒ

３．将平面上每一个点都以红、蓝两色之一染色，证明：存在这样的两个相似三角形，

B B 它们相似比为１９９５，而且每个三角形的三个顶点同色．

1

B B R RR R R O B

高中数学竞赛讲座二试内容19

４．求证：二染色平面上，一定存在一个边长为1或3的正三角形，它的三个顶点同色．（若用三染色平

Ａ(R) 面呢？） 11

（二）．平面图形的染色问题

Ｆ(R) 133Ｂ(W)3113Ｅ(B)

Ｄ(W) Ｃ(B) 31111Ｇ(R) ５．已知⊿ABC为正三角形，G为三条线段AB、BC、CA（包括A、B、C）上的所有点

的集合，将G中的一些点染上黑色，其余点染白色，试证：至少存在一个正三角形 ABC的内接直角三角形，三顶点是同色的． 关键：在AB,BC,CA上取点D,E,F,且ADDB?BFFC?CEEA?2

A（W）

E（B）

D（W） C（W）

则D，E，F必有两点同色，不妨设为E，F同为黑色，

若BC上还有黑色点，命题的证．否则ＢＣ上除点Ｆ全

Ｂ（W） 为白色点，若ＡＢ上有白色点，得证．否则ＡＢ上全为 黑色点，则Ｅ在ＡＢ上的射影Ｇ为黑色点，再在ＡＢ上取 另一点Ｈ，则三角形ＦＧＨ是直角三角形．

F（B） ６．正九边形的一些顶点染上白色，另一些染上黑色．证明：存在两个全等的三角形，每一个三角形的顶

点染有同一颜色．

解：九个顶点中至少有5个顶点颜色相同，设为白色，5个白色顶点能构成10个顶点同为白色三角形，然

后绕正九边形中心旋转，每次旋转

2k?9(k?0,1,?,8)，上述

10个三角形，9次旋转后构成90个三角

形。但正九边形顶点仅能构成C92个不同三角形，因此存在某两个白色，在不同的旋转过程中与某一个三角形重合，则两个白色三角形全等．

７．设圆周上有2n(n?N)个点，将其中n点染成红色，其余n点均染蓝色，则存在n

条该圆的互不相交的弦，每条弦两端分别为上述２n个点中的不同颜色的两点． 证明：若某一组长度和最小的n条线段中，存在相交的两端异色的两弦，设他们为 A1B1,A2B2,且A1,A2为红色点，B1，B2为蓝色点，A1B1?A2B2?O，则

A1B1?A2B2?A1B2?A2B1,而A1B2，A2B1也为两端异色的弦，，故若把前面n条弦中的

2

高中数学竞赛讲座二试内容19

A1B1，A2B2换成A1B2，A2B1所得的

n条弦的长度之和变小，矛盾．

８．在正６n＋１边形中，将k个顶点染成红色，其余顶点染成蓝色．证明：具有同色

顶点的等腰三角形数目不依赖于染色方法．

解：称端点同色的线段为同色线段，否则为异色线段；三顶点同色的同色的等腰三角形为同色，三顶

点异色的等腰三角形为异色等腰三角形．则有

同色等腰三角形的个数＋异色等腰三角形的个数＝等腰三角形的个数＝定值． 由已知对每一条线段，以它为边的等腰三角形恰有３个， 每个异色等腰三角形恰有两条异色线段，则

异色等腰三角形的异色边数之和＝异色等腰三角形的个数×２ ＝异色线段数×３ 故异色三角形的个数＝

32?11异色线段的条数＝Ck． C6n?1?k（为定值）

32９．已知若干红点和若干蓝点，将它们的某些点连成线段．如果在与Ｐ点相连的点中，

与Ｐ点颜色不同的点多于一半，则称Ｐ点为＂奇点＂，若点Ｐ为＂奇点＂，则改变 Ｐ点的颜色，证明：经过有限次这样的操作，一个＂奇点＂也没有．

关键：若Ｐ为奇点，则与Ｐ点相连的点中，与Ｐ点异色的点多于与Ｐ点同色的点，改变Ｐ点颜色后，这组

与Ｐ点相连的点中，与Ｐ点同色的点就多于与Ｐ点异色的点，这一次变化使得与Ｐ点相连的两端异色的线段至少减少一条，即每次操作使整个图形中两端异色的线段至少减少一条．而原来两端异色的线段只有有限条，所以这样的操作只要操作有限次便会使奇点消失．

（三）空间图形的顶点染色问题

１０．设在空间给出２０个点，其中某些点染红色，其余点染蓝色，已知在任何一个平面上的同种颜色点

不会超过３个，求证：存在一个四面体，它的顶点同色，并且至少有一个侧面内不含另一种颜色的点．

三．巩固练习

１．在一条直线上标出n个不同的蓝点和n个不同的红点．证明：同色点两两之间的距离

之和不超过异色点两两之间的距离之和．

２．平面直角坐标系中，设计一种方法将所有整点染白、红、蓝三色之一，使得①各色点出现在无穷多条

平行于横轴的直线上；②对于任意白色点A、红色点B、蓝色点C总可以找到一个红色点D，使ABCD

3

高中数学竞赛讲座二试内容19

使平行四边形．

３．在圆周上给定2n?1(n?N,n?3)个点，从中任选n个点染成黑色，试证明：一定存在两个黑点，使

得以它们为端点的两条弧之一的内部，恰好含有n个所给定的点．

４．任给一个k染色平面，a?0(a?1)，n为大于２的自然数，证明存在两个顶点同色的相似n边形，其

相似比为a．

染色问题与染色方法（二）

一．基本方法

染色问题的本质是对集合的元素进行分类的问题，染色可以使分类更直观、更形象．

染色问题主要有两类：一类使借助染色方法解决问题；二类是问题的条件是用染色的方式给出的．常见的染色问题有对区域的染色（包括对方格，三角形的染色），对线段的染色，对点的染色．常用思想方法是整体思想，抽屉原理，考虑极端情形，数学归纳法，构造思想等．

二．例题精选

（一）线段染色问题

如果一个图形有n个顶点，每两个顶点间连有一条线段（边），则称这个图形为完全图，记为Kn．若每条边染上红蓝两色之一，称之为二染色；每条边都染上k种颜色之一，称之为k染色．如果以图中三个顶点的三角形的三边染有同一种颜色，则称之为同色三角形． 例１．在二染色K6中，总存在两个单色三角形．

A2

A3 A1

A6 A5

A4

例２．试证：在二色K7中至少有四个单色三角形．

4

高中数学竞赛讲座二试内容19

例３．将使每一个k染色的完全图Kn都含有单色三角形的n的最小值记作rk，求证：当 k?2时，有rk?k(rr?1?1)?2． 利用：数学归纳法

例４．平面上有任三点不共线的10个点，两两连线，这些线段已经被染成红、兰两色，

每条线段染一色，已知A点引出的红色线段有奇数条，除A点外其余各点所引出的 红色线段数各不相同，求此图中，三边全红及两边红、一边兰的三角形各有多少个？

例５．空间１８个点，任三点不共线，它们的两两连线染上红色或兰色，每条线段仅染一色．试证明其中

一定存在一个同色的完全四边形．

例６．已知一五棱柱A1A2A3A4A5?B1B2B3B4B5，各棱都被染上红或蓝色，每一条对角线及面对角线也

都被染上红色或兰色，以棱柱顶点为顶点的三角形各边不构成同色三角形，证明：棱柱的两底面五边形的各边同色．

5

高中数学竞赛讲座二试内容19

（二）线段染色方法应用

例７．求证：世界上任何六人中总可以找出三人，他们互相认识或互相不认识．

例８．九名数学家在一次国际数学会议上相遇，他们当中任何三个人中至少有两个人能讲同一种语言，而

且每人最多能讲三种语言，试证明：至少有三个数学家能讲同一种语言．

关键：用k9表示9位数学家，将k9的边染色，当两位数学家不能讲同一种语言时，用s0染色，当两名

数学家同时能讲第i种语言时，用si颜色染色（若能同时讲不止一种语言，则任选一种）．从而得到一个由s0,s1,s2,?染色的完全图k9．由题意得k9不含s0色的单色三角形，与每个顶点相邻的非s0色边至多有３种颜色．要求证的是k9含非s0色的同色三角形．

取k9的一顶点V，若与V相邻的s0色边的条数不超过4，则与V相邻的非s0色边的条数不小于

4，共三种颜色，则存在同色角．若与Ｖ相邻的s0色边的条数不小于４，设VAi(i?1,2,3,4,5)为s0色，则以A1,A2,A3,A4,A5为顶点的k5不含s0的边，从而与A1相邻的４条边至多有３种颜色，故有两条同色边．

例９．现有九个人，已知任意三人中总有两个人互相认识，证明：必有四人互相之间都认识．

例１０．某桥牌俱乐部有个约定：四人在一起打牌，同一方的两人必须曾合作过或都不曾合作过，试证明：

只要有五人，就一定能凑齐四人在一起打牌．

例１１．有十七名科学家，其中每一名和其它所有人通讯，他们在通讯中只讨论三个问题，而且每两位科

学家之间只讨论一个问题．试证明：至少有三位科学家互相之间只讨论同一问题．

例１２．某国际社团成员共有１９９６名，来自六个国家，将他们加以编号为１，２，３,?，１９９６，

则必存在一名成员的编号是其两位同胞的编号之和或其一同胞编号的两倍．

例１３．已知空间有六条直线，其中任何三条中都有两条异面，求证：必有三条直线两两异面． 例１４．在平面上放置六个点，其中任意两点之间的距离都不大于１，求证：其中可以选出三点，使它们

两两之间的距离都小于１．

6

高中数学竞赛讲座二试内容19

例１５．平面上六点，任何三点都是一个不等腰三角形的顶点，求证：这些三角形中有一个的最短边同时

是另一个三角形的最大边．

例１６．两个航空公司为１０个城市通航，使得任何两个城市之间恰有一个公司开设直达航班进行往返服

务，试证至少有一个公司能提供两个相交的旅游圈，每个圈可旅游奇数个城市．

三．练习

１．空间八个点A1,A2,?,A8，任三个点不在一条直线上，它们的两两连线染成红色或兰色，每条线段一

色．求证：必存在三条无公共端点的同色线段．

３．大厅中聚会了１００个客人，他们中每人至少认识６７人，求证：这些客人中一定可找出４个人，他

们之间任两人都彼此认识．

４．连接圆周上９个不同的点的３６条线段染成红色或兰色，每条线段仅染一色，假定由９个点中人三点

所确定的三角形中均含有红边．试证明从中必能找到一个红色的完全四边形．

５．求最小的正整数n，使得在以任意方式的二染色Kn中，总存在两个没有公共边的同色三角形． ６．将K10的边任意去掉n条边后，得到的图任意二染色均含同色三角形，试求满足上述条件的n的最大

值．

染色问题及染色方法（三）解答

一．基本方法

染色问题的本质是对集合的元素进行分类的问题，染色可以使分类更直观、更形象．

染色问题主要有两类：一类使借助染色方法解决问题；二类是问题的条件是用染色的方式给出的．常见的染色问题有对区域的染色（包括对方格，三角形的染色），对线段的染色，对点的染色．常用思想方法是整体思想，抽屉原理，考虑极端情形，数学归纳法，构造思想等．

二．例题精选

（一）边染色

7

高中数学竞赛讲座二试内容19

例１．现有九个人，已知任意三人中总有两个人互相认识，证明：必有四人互相之间都认识．

关键：九个人看成九个点，两两连一线得一k9，两人认识染红色，不认识染兰色，任意一个三角形必有一红色边．

若一点Ａ出发有５条红色线AB1,AB2,AB3,AB4,AB5，易证B1,B2,B3,B4,B5能组成一个红色三角形B1B2B3，则AB1B2B3是完全红色四边形．

若点Ａ发出４条红色线，４条兰色线AB1,AB2,AB3,AB4，则B1B2B3B4是完全红色四边形． 练习：空间１８个点，任三点不共线，它们的两两连线染上红色或兰色，每条线段仅染一色．试证明其中一定存在一个同色的完全四边形．

解：一点P出发有17条线，至少有9条同色，不妨设为PA1,PA2,?,PA9且为红色，若A1,A2,?,A9能组成一个红色三角形，得证．

否则A1,A2,?,A9组成的K9的任意一个三角形至少有一边兰色；由A1发出８条线段，至少有４条同色，若有４条以上（包括４条）红色线段，

R 不妨设为A1A2,A1A3,A1A4,A1A5,?，则A2,A3,A4,A5之间 P 的连线都是兰色线，则A2A3A4A5是同色完全四边形．若A1 发出５条兰色线A1A2,A1A3,A1A4,A1A5,A1A6，则

A2,A3,A4,A5,A6A9 R A8 R R R R R R A1

A2

A3

A4

A5 A7 A6

R 之间连线组成一个兰色三角形．

例２．九名数学家在一次国际数学会议上相遇，他们当中任何三个人中至少有两个人能讲同一种语言，而且每人最多能讲三种语言，试证明：至少有三个数学家能讲同一种语言．

关键：用k9表示9位数学家，将k9的边染色，当两位数学家不能讲同一种语言时，用s0染色，当两名数学家同时能讲第i种语言时，用si颜色染色（若能同时讲不止一种语言，则任选一种）．从而得到一个由

s0,s1,s2,?染色的完全图k9．由题意得k9不含s0色的单色三角形，与每个顶点相邻的非s0色边至多有３

种颜色．要求证的是k9含非s0色的同色三角形．

取k9的一顶点V，若与V相邻的s0色边的条数不超过4，则与V相邻的非s0色边的条数不小于4，共三种颜色，则存在同色角．若与Ｖ相邻的s0色边的条数不小于４，设VAi(i?1,2,3,4,5)为s0色，则以

A1,A2,A3,A4,A5为顶点的k5不含s0的边，从而与A1相邻的４条边至多有３种颜色，故有两条同色边．

（二）区域染色

8

高中数学竞赛讲座二试内容19

例３．设有3×7的棋盘，给每一个方格染上红蓝两色之一，试证明：至少存在一个矩形，它的四个角的小正方形同色（即四角同色矩形）．

例４．设有4×19的棋盘，给每一个小方格染上红、蓝、黄三种颜色之一，试证明：至少存在一个四角同色矩形．

证明：设对4×19棋盘三染色，因为4×19=76，所以至少存在一种颜色至少染了26格，不妨设为红色，设a表示19列中出现红色最多的列中红色的个数，则a可能取值为2，3，4．

当a＝４时，不妨设第一列出现４个红格，余下的至少22个红格，分布在其余的18列中，所以至少存在一列有两红格，它们与第一列的4个红格中同行的两个构成一个四角同色矩形．

当a＝３时，不妨设第一列的前三格全为红格，若后１８列的某一列的第一、二、三行中有两红格，则得证．否则后１８列的３×１８棋盘每列至多有一个红格，对于后１８列中，设其中有两个红格的列的个数

??2x?y?26?3?23?x?(2x?y)?(x?y)?5，因为前３为x，一个红格的列的个数为y，则x,y满足???x?y?19?1?18行的同列至多有一个红格，故五列中两红格只能是１４行，２４行，３４行，所以存在四角红色矩形． 当a＝２时，设有两格红色的列数为x，仅有一格为红色的列数为y，则

??2x?y?26?x?7， ?而两个红格分布于四个不同位置的不同分配方式仅有６种，所以至少存在两

??x?y?19个列的红个构成四角同色矩形． （三）区域染色方法

例６．某班有49名学生，坐成七行七列，每个座位的前后左右均称为它的邻座，要使全班每一个同学都离开自己的座位坐到邻座上去，问这种方案能否实现？

9

高中数学竞赛讲座二试内容19

２５个白格，２４个黑格，所以不可能

例７．证明：用15块大小是4×1的矩形和一块2×2的矩形不能恰好铺盖8×8的方格表．

４×１矩形恰好能覆盖２个黑格，２×２矩形只能覆盖３个或１个黑格，那么１５个４×１矩形与一个２×２矩形只能覆盖３３或３１个黑格，而图形有３２格方格，故不能覆盖．

例8．将正三角形划分成n2个同样大小的小正三角形，把这些小正三角形的一部分标上号码1,2,?,m，并且号码相邻的三角形有相邻的边，求证：m?n2?n?1． 解：将图中的朝下的小正三角形染上兰色，顶点朝上的小三角形 均染上白色，则图中相邻小三角形均不同色．由此可知， 标号１若处于蓝三角形中，那么若标号m在兰色三角形 中，则被标号的兰色三角形个数比被标号的白三角形个 数多１；若标号m在白三角形中，则被标号的两 色三角形个数相同．总之，若标号１在兰色三角形

中，则被标号的三角形总数不超过图中兰色三角形总数的两倍．

同理若标号１处于白三角形中，则被标号的白三角形至多比标号的兰色三角形多一个．从而被标号的三角形总数不超过图中兰色三角形总数的两倍加１． 三．练习

1．对5×16棋盘的每一格染红、黄、蓝三色之一，证明：一定存在一个四角同色矩形．

10

高中数学竞赛讲座二试内容19

２．将12×12棋盘的13×13个格点用三种颜色染色，每点恰染一种颜色，求证：必存在 一个以格点为顶点的四顶点同色的矩形．

3．今有一个11×12的方格纸，共19块1×6和1×7的小矩形，问这19块小矩形能否 恰好覆盖住11×12的方格纸．

4．在１２×１２的超级棋盘上，一匹超级马每步跳至３×４矩形的另一角，问它能否从某点出发遍历每格一次回到出发点？

5．一个n×n棋盘的每一个小方格都被染上m种颜色中的一种，且任意两行都不能染成完全一样．然后对某列上的所有小方格重新染上白色后，任意两行仍然没有完全一样．（反证法）

11

本文来源：https://www.bwwdw.com/article/q4d7.html