《五年级奥数春季实验班第讲组合数学之染色与覆盖（精编版）》由会员分享，可在线阅读，更多相关《五年级奥数春季实验班第讲组合数学之染色与覆盖（精编版）（5页珍藏版）》请在金锄头文库上搜索。
1、第二讲组合数学之染色与覆盖例 1有一次车展共36 个展室，如下图，每个展室与相邻的展室都有门相通，入口和出口如图所示。参观者（填“能”或“不能” ）从人口进去，不重复地参观完每个展室再从出口出来。解：答：不能；如图将展室黑白相间染色，入口为白色，出口也是白色，而走遍36 个展室，从白到黑，再从黑到白， 共走了 35 步，最后应该走到黑格，而出口仍然是白格，矛盾，所以无法完成。例 2棋盘由下图所示的9 个小圆圈排列而成，用19 编号，在 3 号和 9 号的小圆圈中各方一枚棋子，分别代表警察和小偷。若两个小圆圈之间有线相连，则棋子可以从其中一格走入另一格，现在由警察先走，两人轮流，每人每次走一步，
2、每步可以从一格走到有线相连的临格之中。如果在6 步之内警察走入小偷所在的格子中，就算警察抓住了小偷而立功获胜；如果警察走了6 步还没有抓住小偷，就算他失职而失败。问警察应如何取胜。147369258解：警察先从3 走到 1，则小偷从9 走到 7（或 8）；第 2 步，警察走到2，小偷走到6（或 9）；第 3 步，警察走到3，小偷走到7 或 8；第 4 步，警察走到4，小偷走到9；第 5 步，警察6，小偷无论是走到7（或 8），警察在第6 步一定可以获胜。例 3空间六点任三点不共线，任四点不共面，成对地连接它们得到十五条线段，用红色或蓝色染这些线段（一条线段只染一种颜色），求证：无论这么染，总存
3、在一个同色的三角形。解：设六点为A 、B 、C、D、E、F，从 A 点出发的五条线段AB 、AC 、AD 、AE 、AF 中至少有3 条是同色的，不妨设AB 、AC 、AD 为红色，我们再看 BCD 的三边，如果都是蓝色，那么存在同为蓝色的BCD ，若 BCD 中有一条边不是蓝色，而是红色，不妨设BC 是红色，则AB 、AC 、BC 都是红色，这是一个红色三角形。所以总存在一个同色的三角形。例 4下图是由14 个大小相同的方格组成的图形，试问（“能”或“不能” ）剪裁成 7 个由相邻两个方格组成的长方形。解：答：不能；如图，将图形黑白相间染色，则出现8 个黑格， 6 个白格，而相邻的两个方格组
4、成的长方形一定是一黑一白，矛盾，所以无法裁成7 个小长方形。例 5一个 22 正方形和15 个 41 长方形（“能”或“不能” ）拼成 88 的大正方形请说明理由。解：答：不能；1234123423412341341234124123412312341234234123413412341241234123如图进行染色，1 个 41 矩形恰好盖住四种颜色的方格各一个，而1 个 22 矩形方块总不能盖住四种颜色的方格各一个，因此这16 个矩形块盖住的4 种颜色的方格数不同，而图中的四种颜色的方格数是相同的，矛盾。所以用 15 个 41 矩形块和1 个 22 矩形块不能完全覆盖88 矩形。例 6在
5、666 的正方体盒子中最多可以放入个 114 的小长方体这里每个小长方体的面都要与盒子的侧面平行。解：分上下两层，下层高度为4，则 664 中竖着放36 个小长方体；上层高度为2，都只能横着放，每层最多能放入8 个小长方体，所以28=16， 36+16=52 。所以最多放入52 个小长方体。例 7在一个 66 的方格棋盘中， 将若干个11 的小方格染成红色，如果随意划掉3 行 3 列，在剩下的小方格中必定有一个是红色的，那么最少要染个方格。解：先考虑每行每列都有一个红格，比较方便的涂法是在一条对角线上涂6 格红色的（如图1），任意划掉3 行 3 列，可以设想划行划列的原则是：每次划掉的红格越多
6、越好，对于图1，划掉 3 行去掉了 3 个红格，还有3 个红格在3 列中，再划掉3 列就不存在红格了，所以必有一些行一些列要涂2 个红格，为了尽可能的少涂红格，那么每涂一个红色的，一定要使多出一行的同时，也多出一列有两个红色的；先考虑有3 行中有 2 格涂红（如图2），显然，同时必然有3 个列中也有2 格红色的，这时，我们可以划掉有 2 格红色的3 行，还剩下3 行，每行上只有一个涂红，每列上也只有一格涂红，那么再带红格的3列就没有红格了；为了使至少余下一个红格，只要再涂一个红格，此红格要使图中再增加一行一列有两个红格的，如图 3；所以，结论是：至少需要涂红10 个方格例 8将 1515 的正
7、方形方格表的每个格涂上红色、蓝色或绿色。证明至少可以找到两行，这两行中某一种颜色的格数相同。解：假如不存在两行，这两行中某一种颜色的格数相同.则红色在不同的行中应该有不同的格数，所以红色格数至少0+1+2+14 105 个，同样蓝色或绿色的格数都105 个，共计至少315 个格子。但是一共只有1515=225 个格子所以这是不可能的.所以至少可以找到两行，这两行中某一种颜色的格数相同.随堂测试1. 下图是小学素质教育成果展览会的展室，每两个相邻的展室之间都有门相通，有一个人打算从A 室开始依次而入，不重复地看过各室展览之后，仍回到A 室，问他的目的能否达到，为什么AA解：答：不能；将图中方格黑
8、白相间染色，有5 个黑格， 4 个白格，按照这个人的走法，每次从黑格走到白格或者从白格走到黑格，奇数步走入白格，偶数步走入黑格，他从 A 室出发，走遍各室回到A 室，一共走九步，应该最后走到白格，与A 室为黑格矛盾， 所以他的目的不能达到。2. 下图是半张中国象棋棋盘，棋盘上放有一只马，众所周知， 马是走“日”字的。请问：这只马（“能” 或 “不能”）不重复地走遍棋盘上的每一个点，然后回到出发点。马马解：答：不能；将图中的点红蓝相间染色，如图现在马在蓝色点上，按马的走法，它下一步走到的点一定是红色的点， 同样从红色点出发一定走到蓝色的点。所以它走奇数步走到红色点，偶数步走到蓝色点。现在一共有5
9、9=45 个点，该马从蓝色点出发不重复地走遍各点，回到原来的位置，一共走49 步，应该到达红色点，而原来是从蓝色点出发的，矛盾。所以无法完成上述任务。3. 将线段A0An 依次用分点A1， A2， An?1 分成 n 段小线段，将端点A0 和 An 涂成蓝色，中间的分点涂上红色或蓝色，那么在这n 段小线段中，端点异色的小线段的条数为（）A偶数B奇数C不一定解：答：选A，有偶数条端点异色的小线段；如果这 n+1 个点都涂成蓝色，那么图中端点异色的小线段的条数为0 条， 0 是偶数，将中间的n?1 个点中的某一个点变成红色，那么图中端点异色的小线段的条数为2 条， 2 是偶数， 再将剩下的点中某一
10、个点变成红色，如果它与前面的红点相邻，那么图中端点异色的小线段的条数不变，如果它与前面的红点不相邻，那么图中端点异色的小线段的条数增加2 条，总条数仍然是偶数，继续增加红点的个数，如果新添加的红点恰好将原来两个红点之间的蓝点变为变成红点之后，使得原来断开的两部分红点连成一串，那么端点异色的小线段的条数减少2 条，总条数还是偶数。按照这个规律继续添加红点，直到所有的点都成为红色点，总条数还是偶数。4. 下图是有40 个边长为1 的小正方形组成的图形，从它上面最多能剪出个长和宽分别为2 和 1 的长方形。解：答： 19 个；如图将棋盘黑白染色，按现在的染色方法得到21 个黑色的方格和19 个白色的
11、方格，而美国长和宽分别为21 的长方形，需要占一个黑格和一个白格，所以最多剪出19 个长方形。5. 用若干个22 和 33 的小正方形（“能”或“不能”）拼成一个1111 的大正方形请说明理由。解：答：不能；如图将 1111 的大正方形按条形黑白相间染色，现在黑色比白色的小方格多11 个。对于 22 的小正方形，无论如何放置，黑格和白格都一样多，而对于33 的小正方形，可能是6 黑 3白，也可能是3 黑 6 白，它们的差都是3 个，也就是黑白小格的差一定是3 的倍数。而对于可能用到的33 的小正方形的个数，无论是多少个，黑白小格的差都不会是11. 矛盾。所以无法覆盖。6. 如图，把正方体的6
12、个表面均剖分成9 个相等的正方形，现用红、黄、蓝3 种颜色去染这些小正方形， 要求有公共边的正方形所染的颜色不同。那么染成红色的正方形的个数最多是个。解：答案： 22 块；先涂前面的一块，最多可以有5 个小正方形涂成红色，即四角和中心。这时与它相邻的面（如右面）最多有4 块可以涂成红色，如果后面与左面与它们对称染色，则这时已经有(5+4) 2=18 个红格，此时上下面只能各有2 个面染成红色，7在 1000 1000 的方格表中任意选取三角形的顶点。N 的最小值是n 个方格染成红色，都存在。3 个红色方格，它们的中心构成一个直角解：答案： 1999；如果我们在正方形ABCD 的相邻两边，AB、
13、BC 上取除了它们重合的小方格外的9992=1998 个方格， 把它们涂成红色，那么它们的中心都不能构成一个直角三角形的顶点。下面证明任取1999 个方格一定能够成立。先看行，在1000 行中，至少有一些行中至少有两个格子是红色的，那么因为含有0 或 1 个红点的行最多999 个，所以其他行含有红点肯定大于等于1999?999=1000， 如果是大于1000，那么根据抽屉原理，肯定有两个这样红点在一列，那么就会出现红色三角形；如果是等于1000 而没有这样的2 个红点在一列，说明有999 行只含有1 个红点，而剩下的一行全是红点，那也肯定已经出现直角三角形了，所以n 的最小值为1999.8大厅
14、中聚集了100 个客人，他们中每人至少认识67 个人，证明在这些客人中一定可以找到4 人，他们之中任何两人都彼此相识。证明：在其中先确定A， A 至少认识67 人，有不多于32 人（ 99?67=32）不认识；在这 67 人中选定B， A 与 B 认识， B 除了认识 A 之外，如果他还认识其他的32 人，那么在原来的67人中他至少还认识67?32?1=34（人），有不多于32 人（ 67?1?34=32 人）不认识， 在这 34 人中选定C，于是 A、B、C 两两认识。C 除了认识A、B 之外，还认识A、B 和 A 不认识的32 人，以及A 认识、 B 不认识的32 人，而 C 也认识 67 人，67?2?32?32=1，说明 C 应该在 A、B 都认识的34 人中至少还认识1 人，设此人为 D ， 则 A、B、C、D 都相识。
