染色问题(2)

高中数学竞赛讲座二试内容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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库染色问题(2)在线全文阅读。