五级下册奥数试题组合数学之染色与覆盖全国通用.docxVIP

精品word 精品word 精品word PAGE / NUMPAGES 组合数学之染色与掩盖 例1．有一次车展共36个展室，如以下图，每个展室与相邻的展室都有门相通，入口和出口如下图。参观者 〔填“能〞或“不能〞〕从人口进去，不重复地参观完每个展室再从出口出来。 解：答：不能； 如图将展室黑白相间染色，入口为白色，出口也是白色，而走遍36个展室，从白到黑，再从黑到白，共走了35步，最终应当走到黑格，而出口仍旧是白格，冲突，所以无法完成。 例2．棋盘由以下图所示的9个小圆圈排列而成，用1~9编号，在3号和9号的小圆圈中各方一枚棋子，分别代表警察和小偷。假设两个小圆圈之间有线相连，那么棋子可以从其中一格走入另一格，现在由警察先走，两人轮番，每人每次走一步，每步可以从一格走到有线相连的临格之中。假设在6步之内警察走入小偷所在的格子中，就算警察抓住了小偷而立功获胜；假设警察走了6步还没有抓住小偷，就算他失职而失败。问警察应如何取胜。 解：警察先从3走到1，那么小偷从9走到7〔或8〕；第2步，警察走到2，小偷走到6〔或9〕； 第3步，警察走到3，小偷走到7或8；第4步，警察走到4，小偷走到9； 第5步，警察6，小偷无论是走到7〔或8〕，警察在第6步肯定可以获胜。 例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个白格， 而相邻的两个方格组成的长方形肯定是一黑一白，冲突，所以无法裁成7个小长方形。 例5．一个2×2正方形和15个4×1长方形 〔“能〞或“不能〞〕拼成8×8的大正方形？请说明理由。 解：答：不能； 1 2 3 4 1 2 3 4 2 3 4 1 2 3 4 1 3 4 1 2 3 4 1 2 4 1 2 3 4 1 2 3 1 2 3 4 1 2 3 4 2 3 4 1 2 3 4 1 3 4 1 2 3 4 1 2 4 1 2 3 4 1 2 3 如图进行染色， 1个4×1矩形恰好盖住四种颜色的方格各一个，而1个2×2矩形方块总不能盖住四种颜色的方格各一个，因此这16个矩形块盖住的4种颜色的方格数不同，而图中的四种颜色的方格数是相同的，冲突。 所以用15个4×1矩形块和1个2×2矩形块不能完全掩盖8×8矩形。 例6．在6×6×6的正方体盒子中最多可以放入 个1×1×4的小长方体？这里每个小长方体的面都要与盒子的侧面平行。 解：分上下两层，下层高度为4，那么6×6×4中竖着放36个小长方体； 上层高度为2，都只能横着放，每层最多能放入8个小长方体，所以2×8=16， 36+16=52。所以最多放入52个小长方体。 例7．在一个6×6的方格棋盘中，将假设干个1×1的小方格染成红色，假设任凭划掉3行3列，在剩下的小方格中必定有一个是红色的，那么最少要染 个方格。 解：先考虑每行每列都有一个红格，比较便利的涂法是在一条对角线上涂6格红色的〔如图1〕， 任意划掉3行3列，可以设想划行划列的原那么是：每次划掉的红格越多越好，对于图1，划掉3行去掉了3个红格，还有3个红格在3列中，再划掉3列就不存在红格了， 所以必有一些行一些列要涂2个红格，为了尽可能的少涂红格，那么每涂一个红色的，肯定要使多出一行的同时，也多出一列有两个红色的； 先考虑有3行中有2格涂红〔如图2〕，明显，同时必定有3个列中也有2格红色的，这时，我们可以划掉有2格红色的3行，还剩下3行，每行上只有一个涂红，每列上也只有一格涂红，那么再带红格的3列就没有红格了； 为了使至少余下一个红格，只要再涂一个红格，此红格要使图中再增加一行一列有两个红格的，如图3；所以，结论是：至少需要涂红10个方格． 例8．将15×15的正方形方格表的每个格涂上红色、蓝色或绿色。证明至少可以找到两行，这两行中某一种颜色的格数相同。 解：假设不存在两行，这两行中某一种颜色的格数相同. 那么红色在不同的行中应当有不同的格数，所以红色格数至少0+1+2+……+14＝105个， 同样蓝色或绿色的