《棋盘染色法的分类与应用.doc》由会员分享，可在线阅读，更多相关《棋盘染色法的分类与应用.doc（9页珍藏版）》请在三一文库上搜索。
1、棋盘染色法的分类与应用华师大二附中 王崇熙指导教师 施洪亮摘 要组合数学是数学应用中非常重要的一门分支，染色法是其中非常重要的一种方法，随着染色法的发明，一大系列难解的组合问题都得到了非常简便地解决，本研究着重将过去比较模糊的染色法的概念做了一个系统的分类，创造了一种可行的发现新的染色方案的比较系统的思想，并将普遍的二维染色法做了一个推广，解决了一个三维中的组合问题。研究得出的主要结论为：1、 二维染色法的分类：（1） 双色染色法（国际象棋盘染色法）；（2） 多色规则染色法（高度对称）；（3） 不规则染色法（根据问题灵活转变）；2、 三维染色法的初步结论：三维染色法基于二维的一些情况进行推广，
2、解决了一个较为困难的三维覆盖问题。关键词：染色法；博弈问题；覆盖问题；分类；推广一、引言：组合数学是一门研究离散的量的变化规律的学科。组合数学的方法千变万化，没有一种适用于所有问题。这些方法有一些共同点：1、所有的方法追求的是简单与清晰。2、所有的方法都较难想到，而说破了却又很简单，解决问题后经常有一种恍然大悟的感觉。作为一名数学爱好者，很多人喜欢解组合数学的问题，其中染色法是颇受欣赏的方法。但是在中学或大学数学教与学的过程中缺乏对染色法的系统研究，这使得人们很难学习与掌握该方法。做题时并不能真正的掌握问题的本质，在下一次遇到可能用染色法解决的问题时并不能很好地找到正确的解决方法。我们不妨来看
3、一下过去使用染色法解决问题的过程，一道问题的解答一半多以这样开头：“这道问题我们用染色法来解决，把点A涂上红色，如图，分析一下各类不变量，我们得到”。在做了大量的练习之后，笔者初步掌握了棋盘染色方法，对该染色法进行了分类，并研究了该染色法在解决组合问题中的具体应用。二、棋盘染色法的分类: 棋盘染色法是一类借助国际象棋棋盘通过染色解决组合问题的解踢方法的简称。经过对染色法问题的系统研究，分析每种方法的解题特点，经过归纳整理，可将棋盘染色法大致分为以下几类：1、 双色相邻染色法（国际象棋棋盘染色法）这个染色法的基本构图（如右图），正如它的名字所言，是分析问题的奇偶本质。我们可以发现这种染色法得到的
4、一个图像有以下几个特点：（1） 这张图具有高度的对称性，不管是平移还是旋转或是翻折，都无法改变它的性质。（2） 这张图总体来说黑白格子的个数相等，关键的一点是，所有的黑格都只与白格相邻，同样所有的白格都只与黑格相邻。于是，在这张图中任何一条格子到格子之间的路径都经过几乎相同的黑白格数，至多相差一个；在这张图内任取一块以黑白格子的边界为边界的区域所包含的黑白格数也至多只相差一个，这就导致了一个很强的性质。2、 多色染色法多色染色法的基本构图（右图为三色染色）：该构图的特点如下：（1）类比与双色染色法，多色染色法也有高度的对称性，只是缺少了翻折对称性。（2）这张图中所有颜色的格子的个数全都相同，但
5、各种颜色的格子只与两种颜色的格子相邻。在这类图中没有二色染色中非常强的性质，但令人意外的是，它却能解决不少有关于模n性质的问题。3、 不规则染色法不规则染色法的构图（这种染色法的构图不唯一，右图为一个简单的例子）：特点如下：（1） 灵活多变，没有明确的形式。（2） 问题的解决明快，简单，但不容易想到。右图在用这个图形 覆盖时就有非常有用的特点，永远覆盖到奇数个黑格。三、棋盘染色法的推广三维染色法 一般来说，棋盘染色法都只在二维的范围内应用，但若将棋盘一个一个叠放在一起就构成了一个三维的图形，这就导致了三维染色的可能。三维染色法是基于二维染色法的一些情况进行推广，方法更多变。在后文中有一个较为成
6、功的染色法的例子，它解决的是三维覆盖的问题。四、棋盘染色法的应用1、双色染色法的应用问题1一个5*5的房间网，相邻房间是相通的，问能否从箭头房间进入走遍整个房间网并且不重复的走入一个房间？右图黑线就是这样一条路径。这个问题的可以这样来考虑，5*5=25是一个奇数，可以利用染色法尝试，由前面所推得的性质3得到：这条路径所经过的黑白格的格数相差至多为1，但是若走遍整个房间网的话，黑白格数不是也只相差1吗？又由题意发现，起点在黑格，无论终点在黑格还是白格，都无法使白格数多于黑格数，于是，不存在这样的路径。有这个问题了以后，自然的想到了推广，若是用1*2的小方块覆盖棋盘的话会有什么结果，巧的是，有一个
7、著名的银行家曾经提出过类似的问题，下面的问题就来自那位银行家。问题2一个8*8的格子纸，去掉对角两格，是否能用1*2的方块来覆盖它？第一个思路就是看总格数能否被2整除，答案是可以。这个问题曾经困扰过许多人，在没有染色法以前，一般想到的都是半枚举的做法，这个做法一般为（如右下图），一行一行的去试，根据行与行之间的关系来推导出下一行于下一行之间的关系，而不久就发现这个办法不可行，因为一行有七八个格子，至少有10种可能性，10的8次方是一个巨大的天文数字，一秒算一下的话也要两年多。当计算机被发明了之后，利用计算机强大运算功能的想法就逐渐发展起来，当搜索完备了之后虽然也可行，但是一旦行数增加上去之后发
8、现搜索量呈几何级数上升，方法不可行。但问题的描述是那么简单，难道就没有好方法了吗？问题本质是1*2的方块的覆盖，这启示我们问题基于的是奇偶性，我们把1*2的方块盖于国际象棋棋盘之上后发现，由于黑的方格只与白的方格相邻，所以不管怎么放都灰盖住以黑一白两块，这是一个重大的突破，我们数一下原问题中的黑白格数，发现黑格比白格少两个！于是该图形不可被1*2的方块覆盖。这个结论同时也引发了新的问题，如果1*2的方块无法被覆盖的条件是黑白格数不等，如果是1*3的条状方块呢？1*n呢？这个问题就要用到多色染色法了。2、多色染色法的应用问题3 一个8*8的格子纸，去掉右下角的一格，问能否用1*3的方块覆盖它？如
9、果用1*3的方块覆盖的话，我们发现，不管方块如何摆放，都将覆盖住一个黑的格子，一个灰的格子，和一个白的格子。如果这三种颜色的格子数不相同的话，就无法将整个方格覆盖满。题中黑的格子有21个，白的有22个，灰的只有20个，于是无法用1*3的方块覆盖。这种简单的覆盖问题可以推广到1*n。问题4一个无限大的棋盘中有一个由棋子组成的m*n的矩形，一种操作称之为跳是指一个棋子间隔一个棋子跳入一个没有棋子的空档，只认可横向和竖向的跳，比如说（见右图），问当且仅当m，n为何值时能将这个游戏跳到只剩一个棋子？这个问题就不是那么容易想了，由于同上述覆盖问题不同，这个问题并没有十分明显的提示应该使用染色法，但有一点
10、是肯定的，这个问题也是在棋盘上的组合题。开始研究时笔者遇到了一些困难。由于它是操作题，所以一般先从简单的情况进行着手。首先考虑小一点的m和n，通过实际的操作，笔者发现，对小的m与n当且仅当m*n不是3倍数时可以跳到最后那一步，于是这使笔者产生了联想，可能3倍数不可行的证明可以考虑用染色法。先要看一下这个问题的最简单也是最基本的一项操作，问题基于基本的操作步骤“跳”，跳这个步骤涉及到三个格子，有三色染色法性质，这三个一定是三个不同颜色的格子，于是，白格和灰格中各少一个棋子，黑格中增加一个棋子，这样一来，三种颜色的格子中的棋子个数之差的的改变量就是0或2，这就提示我们去考虑在黑白灰各色格中棋子的总
11、数之间的奇偶关系，我们发现，不管进行多少次操作，棋子个数的奇偶关系都不会改变，即原来相同的仍然相同，原来不同的仍然不同，若m*n是3的倍数，则在黑格，白格，灰格中的棋子个数奇偶性相同，但由于不可能将所有的棋子消去，于是，只可能将棋子的个数减至2个，于是问题简单的被解决了。3、不规则染色法的应用问题5现有一个n*m的方阵，下要求满足能用这个图形覆盖方阵的m与n所必须满足的充要条件？这个问题用我们已经用过的方法比较难解出，于是就需要考虑第三种不规则染色法，这种染色法需要根据题目的条件灵活运用。这种方法只能基于不同的题目条件，所以我们必须仔细分析题目中的条件。对于这个问题，首先想到可以将题目所给的图
12、形进行初始的分析，不难发现，问题等价于用这个图形 和这个图形来覆盖整个方阵。这两个图形有什么性质呢？先用简单想到的国际象棋染色法，但不幸的是这个方法没有成功。那么，为什么不成功呢，这是因为这两个图形都是比较对称的，相对于二色染色的对称性几乎是相同的，所以我们要另辟蹊径。这个图形在4*4的概念下对称形有较大的不同，所以我们考虑以4*4位对称单元的染色方案，在对m，n较小的情况下只有当m或n是12的倍数时或m*n是8的倍数时满足条件，于是我们寄希望以证明对某一种染色方案是这两种图形只能覆盖奇数个染色方块，于是我对4*4内的染色方案进行枚举，最后发现，如右图的染色法能满足我们的条件，整体上看是这样一
13、个效果。无论是第一种图形还是第二种图形，都只能在图中覆盖奇数个黑格，于是这个问题有了完备证明。这个问题体现了染色方法的技巧性，而下一个问题能体现染色法之中的优与劣。 问题6 一个国际象棋的棋盘（8*8的正方形），将1到64填入所有的格子中，下进行如下操作，对其中的3*3或4*4的方块内的数同时加一或同时减一，问能否有一种填法使无论如何操作，都无法将表中的所有数字全部变为零？这个问题有一定的难度，所有用不规则染色法来解的问题都有一定的难度，首先考虑最基础的元素，即3*3的方块（先考虑3*3的问题），当下面对这类问题有用的染色方案一般能使最基础的元素具有特殊的特点，较令人期待的是有一部分格子在这类
14、改变下奇偶不变。于是笔者凭直觉对一部分染色方案进行了测试，最先发现的染色方案如右图，图中任何一块3*3的方块都包含4个黑格，于是，只要使填在这36个中的数之和是奇数，则每次操作都不会改变这个和的奇偶性，于是，这36个格子就不可能全部为零，那么问题的答案就是否定的了。但是这幅图能否适用于4*4方块操作的问题呢？答案是否定的。因为4*4的方块不仅能覆盖奇数个黑格，还能覆盖偶数个黑格，那么，没办法，只能另辟蹊径。笔者又对一系列染色方案进行了测试，发现了一种能解决4*4的方案（如右图），此时，笔者又将3*3的方块覆盖于图上意外地发现这张图也能解决3*3时候的操作问题，这究竟是巧合还是有原因的？ 我仔细
15、分析了一下这张图，发现这样一个特点：这张图用4*4方块来分隔以后呈现的是轴对称，用3*3的方块来分割的话是平移对称，两者又都是中心对称。这真是一种奇特的性质，这导致了使用这种染色策略能够一举两得。这才是染色方案中的佳品。4、 三维染色法的创造如果将二维棋盘推广为三维棋盘空间，染色法又如何应用呢？我自行改编了这样一个可能性问题。问题1一个9*15*24的三维立方块，问用这样的立体图形（在点的方块下还有一个方块）能否组成原立体图形？三维的染色法比较难设计，但根据二维已经得到的结论可以将它推广致三维，为了达到证明问题的目的，笔者首先来研究一下问题中的最小而又最重要的组成单元。这个组成单元是有两层构成
16、的，上面一层由三个格子，下面一层有一个格子。笔者希望建立一种对应关系，使这种立体图形在覆盖时具有一一对应的性质，在二维中，一般使用双色染色法来解决问题，笔者发现在这个立方体中有一个侧面正好是一个双奇数的侧面，即双色染色后黑白格数不一样，于是，在二维的基础上进行推广，得到了这样一个三维的染色策略（如右图）。 9 在另一维上则相同的复制24层，这样就得到了一个完整的9*15*24的长方体。在这种染色方案的帮助下，用题中的三维图形进行覆盖时，都将覆盖2个白格和两个黑格，而这张图中黑格的数量比白格多24个，从而无法用题中的三维图形覆盖。问题15至此得到圆满解决。最后我来总结一下方法性的结论：（1） 搞清楚问题的本质，即是关键性的元素究竟具有什么样的性质。（2） 根据这些元素的性质，尽量选择对称性较大的分割。（3） 在这些较为明确后，在小范围里利用枚举来解决问题。参考书目：1、 华罗庚数学竞赛课本（中国大百科全书出版社）2、 奥数教程1，2，3册（华师大出版社，2000）3、 大学组合数学基本教程（2）（3）（4） （5） （注：可编辑下载，若有不当之处，请指正，谢谢!）（6）（7）（8） （9） （10）1、