五年级奥数春季实验班第讲组合数学之染色与覆盖

1、第二讲组合数学之染色与覆盖例1.有一次车展共 36个展室，如下图，每个展室与相邻的展室都有门相通，入口和出口如图所示。参观（填“能”或“不能”）从人口进去，不重复地参观完每个展室再从出口出来。解：答：不能；如图将展室黑白相间染色，入口为白色，出口也是白色,而走遍36个展室，从白到黑，再从黑到白,共走了 35步，最后应该走到黑格，而出口仍然是白格，矛盾，所以无法完成。例2.棋盘由下图所示的 9个小圆圈排列而成，用 19编号，在3号和9号的小圆圈中各方一枚棋子，分别 代表警察和小偷。若两个小圆圈之间有线相连，则棋子可以从其中一格走入另一格，现在由警察先走，两人轮流，每人每次走一步，每步可以从一格走

2、到有线相连的临格之中。如果在6步之内警察走入小偷所在的格子中，就算警察抓住了小偷而立功获胜；如果警察走了 警察应如何取胜。6步还没有抓住小偷，就算他失职而失败。问解:警察先从 第3步, 第5步,若 BCD中有一条边不是蓝色，而是红色，不妨设 红色三角形。所以总存在一个同色的三角形。BC是红色，则 AB、AC、BC都是红色，这是一个例4.下图是由14个大小相同的方格组成的图形，试问 方格组成的长方形。（“能”或“不能”）剪裁成7个由相邻两个3走到1,则小偷从9走到7 （或8）;第2步，警察走到2,小偷走到6 （或9）;警察走到3,小偷走到7或8;第4步，警察走到4,小偷走到9;警察6,小偷无论是

3、走到 7（或8）,警察在第6步一定可以获胜。例3.空间六点任三点不共线，任四点不共面，成对地连接它们得到十五条线段，用红色或蓝色染这些线段（一条线段只染一种颜色），求证：无论这么染，总存在一个同色的三角形。解：设六点为 A、B、C、D、E、F,从A点出发的五条线段 AB、AC、AD、AE、AF中至少有3条是同色 的，不妨设AB、AC、AD为红色，我们再看 BCD的三边，如果都是蓝色，那么存在同为蓝色的BCD,解：答：不能；如图，将图形黑白相间染色，则出现8个黑格，6个白格，而相邻的两个方格组成的长方形一定是一黑一白，矛盾，所以无法裁成7个小长方形。例5. 一个2X2正方形和15个4X1长方形

4、（“能”或“不能”）拼成8刈的大正方形请说明理由。 解：答：不能；1234123423412341341234124123412312341234234123413412341241234123如图进行染色,1个4X1矩形恰好盖住四种颜色的方格各一个，而1个2X2矩形方块总不能盖住四种颜色的方格各一个，因此这16个矩形块盖住的4种颜色的方格数不同，而图中的四种颜色的方格数是相同的，矛盾。所以用15个4X1矩形块和1个2X2矩形块不能完全覆盖 8X8矩形。例6.在6X6X6的正方体盒子中最多可以放入 个1X1X4的小长方体这里每个小长方体的面都要与盒 子的侧面平行。解：分上下两层，下层高度为 4

5、,则6 >6X4中竖着放36个小长方体；上层高度为2,都只能横着放，每层最多能放入8个小长方体，所以2X8=16,36+16=52。所以最多放入52个小长方体。例7.在一个6X6的方格棋盘中，将若干个1X1的小方格染成红色， 如果随意划掉3行3歹U,在剩下的小方 格中必定有一个是红色的，那么最少要染个方格。解：先考虑每行每列都有一个红格，比较方便的涂法是在一条对角线上涂6格红色的（如图1）,任意划掉3行3歹U,可以设想划行划列的原则是：每次划掉的红格越多越好，对于图 1,划掉3行去掉了 3个红格，还有3个红格在3列中，再划掉3列就不存在红格了，所以必有一些行一些列要涂 2个红格，为了尽可

6、能的少涂红格，那么每涂一个红色的，一定要使多出一行的同时，也多出一列有两个红色的；先考虑有3行中有2格涂红（如图2）,显然，同时必然有 3个列中也有2格红色的，这时，我们可以 划掉有2格红色的3行，还剩下3行，每行上只有一个涂红，每列上也只有一格涂红，那么再带红格的3列就没有红格了；为了使至少余下一个红格，只要再涂一个红格，此红格要使图中再增加一行一列有两个红格的，如图3;所以，结论是：至少需要涂红10个方格.例8.将15X15的正方形方格表的每个格涂上红色、蓝色或绿色。证明至少可以找到两行，这两行中某一种 颜色的格数相同。解：假如不存在两行，这两行中某一种颜色的格数相同则红色在不同的行中应该

7、有不同的格数，所以红色格数至少0+1+2+14= 105个，同样蓝色或绿色的格数都 105个，共计至少315个格子。但是一共只有 15X15=225个格子 所以这是不可能的.所以至少可以找到两行，这两行中某一种颜色的格数相同随堂测试1 .下图是小学素质教育成果展览会的展室，每两个相邻的展室之间都有门相通，有一个人打算从A室开始依次而入，不重复地看过各室展览之后，仍回到 A室，问他的目的能否达到，为什么解：答：不能；将图中方格黑白相间染色，有 5个黑格，4个白格，按照这个人的走法，每次从黑格走到白格或者从白 格走到黑格，奇数步走入白格，偶数步走入黑格，他从A室出发，走遍各室回到 A室，一共走九步

8、，应该最后走到白格，与A室为黑格矛盾，所以他的目的不能达到。2 .下图是半张中国象棋棋盘， 棋盘上放有一只马，众所周知，马是走“日”字的。请问：这只马(“能”个点，然后回到出发点。解：答：不能；将图中的点红蓝相间染色，如图现在马在蓝色点上，按马的走法，它下一步走到的点一定是红色的点，同样从红色点出发一定走到蓝色的点。所以它走奇数步走到红色点，偶数步走到蓝色点。现在一共有5X9=45个点，该马从蓝色点出发不重复地走遍各点，回到原来的位置，一共走 49步, 应该到达红色点，而原来是从蓝色点出发的，矛盾。所以无法完成上述任务。3 .将线段AoAn依次用分点Al, A2,，An?1分成n段小线段，将端

9、点 A0和An涂成蓝色，中间的分点涂上红色或蓝色，那么在这 n段小线段中，端点异色的小线段的条数为（）A.偶数 B.奇数 C.不一定解：答：选A,有偶数条端点异色的小线段；如果这n+1个点都涂成蓝色，那么图中端点异色的小线段的条数为0条，0是偶数，将中间的n?1个点中的某一个点变成红色，那么图中端点异色的小线段的条数为2条，2是偶数，再将剩下的点中某一个点变成红色，如果它与前面的红点相邻，那么图中端点异色的小线段的条数不变，如果它与前面的红点不相邻，那么图中端点异色的小线段的条数增加2条，总条数仍然是偶数，继续增加红点的个数，如果新添加的红点恰好将原来两个红点之间的蓝点变为变成红点之后，使得原

10、来断开的两部分红点连成一串，那么端点异色的小线段的条数减少2条，总条数还是偶数。按照这个规律继续添加红点，直到所有的点都成为红色点，总条数还是偶数。4 .下图是有40个边长为1的小正方形组成的图形，从它上面最多能剪出 个长和宽分别为2和1的 长方形。如图将棋盘黑白染色，按现在的染色方法得到21个黑色的方格和19个白色的方格，而美国长和宽分别为 2X1的长方形，需要占一个黑格和一个白格，所以最多剪出19个长方形。5 .用若干个2X2和3X3的小正方形 （“能”或 “不能”）拼成一个11 X11的大正方形请说明理由。如图将11X11的大正方形按条形黑白相间染色，现在黑色比白色的小方格多11个。对于

11、2X2的小正方形，无论如何放置，黑格和白格都一样多，而对于3X3的小正方形，可能是 6黑3白，也可能是3黑6白，它们的差都是 3个，也就是黑白小格的差一定是3的倍数。而对于可能用到的30的小正方形的个数，无论是多少个，黑白小格的差都不会是11.矛盾。所以无法覆盖。6 .如图，把正方体的 6个表面均剖分成9个相等的正方形，现用红、黄、蓝3种颜色去染这些小正方形，要求有公共边的正方形所染的颜色不同。那么染成红色的正方形的个数最多是 个。解：答案：22块；先涂前面的一块，最多可以有5个小正方形涂成红色，即四角和中心。这时与它相邻的面（如右面）最多有4块可以涂成红色，如果后面与左面与它们对称染色，则这

12、时已经有（5+4） >2=18个红格，此时上下面只能各有2个面染成红色，7 .在1000 M000的方格表中任意选取 n个方格染成红色，都存在 3个红色方格，它们的中心构成一个直角 三角形的顶点。N的最小值是。解：答案：1999;如果我们在正方形 ABCD的相邻两边，AB、BC上取除了它们重合的小方格外的999X2=1998个方格，把它们涂成红色，那么它们的中心都不能构成一个直角三角形的顶点。下面证明任取1999个方格一定能够成立。先看行，在1000行中，至少有一些行中至少有两个格子是红色的，那么因为含有0或1个红点的行最多999个，所以其他行含有红点肯定大于等于1999?999=1000,如果是大于1000,那么根据抽屉原理，肯定有两个这样红点在一列，那么就会出现红色三角形；如果是等于1000而没有这样的2个红点在一列，说明有 999行只含有1个红点，而剩下的一行全是红点，那也肯定已经出现直角三角形了，所以n的最小值为1999.8 .大厅中聚集了 100个客人，他们中每人至少认识67个人，证明在这些客人中一定可以找到4人，他们之中任何两人都彼此相识。证明：在其中先确定 A, A至少认识67人，有不多于32人（99?67=32）不认识；在这67人中选定B, A与B认识，B除了认识A之外