国家集训队2003论文集 方奇

《国家集训队2003论文集 方奇》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、染色法和构造法在棋盘上的应用广东北江中学方奇1基本概念2棋盘的覆盖(1)同形覆盖(2)异形覆盖(3)小结3马的遍历(1)马的哈密尔顿链(2)马的哈密尔顿圈4其它问题(1)Wormworld5结语目录●构造法直接列举出某种满足条件的数学对象或反例导致结论的肯定与否定，或间接构造某种对应关系，使问题根据需要进行转化的方法，称之为构造法。●染色法用不同颜色对棋盘格子进行染色，起到分类的效果。类似国际象棋盘上的黑白二染色，称为“自然染色”。●棋盘所谓m*n棋盘，指由m行n列方格构成的m*n矩形。每个方格成为棋盘的格，位于第i行j列的格记为a(i,j)。当i+j为奇（偶）数时，称a(i,j)

2、为奇（偶）格。1基本概念2棋盘的覆盖棋盘的覆盖指用若干图形去覆盖棋盘。覆盖的每个图形也由若干格子组成，称为覆盖形。约定任两个覆盖形互不重叠，任一覆盖形中任一格总与棋盘上某格重合。按覆盖效果，可分为完全覆盖、饱和覆盖、无缝覆盖和互异覆盖。完全覆盖：各个覆盖形的总格子数等于棋盘的总格子数按覆盖形，可分为同形覆盖（只有一种覆盖形）和异形覆盖（有多种覆盖形）。2-1同形覆盖例1给出m,n,k，试用若干1*k的矩形覆盖m*n的棋盘。分析有定理1：m*n棋盘存在1*k矩形的完全覆盖的充分必要条件是k

3、m或k

4、n。证明：充分性是显然的。用构造法。当k

5、n时，每一行用n/k个1*k的矩形恰好完全覆

6、盖。k

7、m情况类似。必要性。当n,m均不能被k整除时，设m=m1*k+r,0=s(否则旋转90°)2-1同形覆盖m=m1*k+rn=n1*k+sr>=s2-1同形覆盖由上面的定理1，可彻底解决m*n棋盘的p*q矩形完全覆盖问题定理2m*n棋盘存在p*q矩形的完全覆盖充分必要条件是m,n满足下列条件之一：（i）p

8、x且q

9、y（ii）p

10、x,q

11、x,且存在自然数a,b，使y=ap+bq其中{x,y}={m,n}2-2异形覆盖例2设有m*n的棋盘，当m*n为奇数时，尝试删去一个格子，剩下部分用若干1*2的矩形覆盖；当m*n为偶数时，尝试删去两

12、个格子，剩下部分用若干1*2的矩形覆盖。分析：1先来考虑m*n为奇数的情况一方面，将棋盘自然染色。无论怎么放，一个1*2的矩形必盖住一个黑格和一个白格，而棋盘上的黑格比白格多1，于是只能去掉一个黑格(即偶格)。2-2异形覆盖另一方面，设去掉偶格为a(i,j)，用构造法必能得到可行解i与j同为奇数i与j同为偶数2-2异形覆盖２再考虑m*n为偶数的情况类似地，由自然染色法得知，去掉的两格必定异色，即一个奇格，一个偶格（不然两种格子总数不等）另一方面，用构造法，总可以用一些粗线将棋盘隔成宽为1的长条路线，使从任一格出发可以不重复地走遍棋盘并回到出发点。2-2异形覆盖针对染色法，上面的例子

13、都是利用“各类颜色格子总数必须相等”这一条件推出矛盾，但有些时候，只考虑这个条件是不够充分的。例38*8棋盘剪去哪个方格才能用21个1*3的矩形覆盖？分析考虑到对称性，　只有剪去a(3,3)、a(3,6)、　a(6,3)、a(6,6)中的某一个　才能满足题意。蓝色：21个白色：22个黑色：21个覆盖类问题其实是一个难度较大的课题，这里只讨论了一些简单的情况，以说明染色法与构造法的应用需要补充的是，染色法的种类形形色色、五花八门。考虑到可推广性和易操作性，本文只着重研究了“间隔染色法”（即自然染色法的推广）2-3小结3马的遍历马行走规则从2*3的矩形一个角按对角线跳到另一个角上马的遍

14、历从一个格出发按跳马规则不重复地走遍所有格棋盘中马的遍历问题分两类(1)马的哈密尔顿链(2)马的哈密尔顿圈3-2马的哈氏链通常有三种方法１贪心法——每一步跳向度最小的点（度数指可一步到达且未经过的点的个数）２分治法——将棋盘分成几个小棋盘，分别找哈氏链，再接起来３镶边法——先在一个小棋盘中找到哈氏链，然后在棋盘四周镶边，已产生大棋盘的哈氏链。按上述方法不难得到下面结论：n*n棋盘存在哈氏链的充要条件是n>3。3-2马的哈氏圈例4求n*n棋盘的哈氏圈分析：将棋盘自然染色，考察无解情况。马无论怎么走，都必须按黑格－白格－黑格－白格．．．．．．如此循环。由于要回到起点（起点与终点同色），

15、途经两种颜色的格子数必相等，可知n为奇数时无解。因为大小限制，n<6时也无解马马马马马马马马马3-2马的哈氏圈当n>=6且为偶数时，用镶边法构造n*n的大矩形是由(n-4)*(n-4)的小矩形套上一个宽为2的环组成的。而宽为2的环有一个特点，就是可用四条回路A、B、C、D刚好覆盖假设(n-4)*(n-4)的棋盘已找到哈氏圈那么只要设法将A、B、C、D四条回路嵌入其中，则n*n的矩形的哈式圈就构造出来了3-2马的哈氏圈1）n除以4余2时，在内矩形四个角（A、E、I、M）