棋盘覆盖与染色法.PDF

林嘉怡 胡薇 蒲昭昭 1、棋盘覆盖与染色法 ——蒲昭昭 2 、骑士巡游问题 ——林嘉怡、胡薇 棋盘覆盖问题 染色法 应用 棋盘：所谓m*n棋盘，指由m行n列方格构成的 m*n矩形。每个方格成为棋盘的格，位于第i行j 列的格记为a(i,j)。当i+j为奇（偶）数时，称 a(i,j)为奇（偶）格。 棋盘覆盖问题：指用若干图形去覆盖棋盘；覆 盖的每个图形由若干格子组成，称为覆盖形； 约定任两个覆盖形互不重叠，任一覆盖形中任 一格总与棋盘上某格重合。 按覆盖效果，可分为完全覆盖、饱和覆盖、无 缝覆盖和互异覆盖  完全覆盖：各个覆盖形的总格子数等于棋盘的总格 子数 按覆盖形，可分为同形覆盖和异形覆盖  同形覆盖：只有一种覆盖形  异形覆盖：有多种覆盖形  用不同颜色对棋盘格子进行染色，起到分类的 效果。类似国际象棋盘上的黑白二染色，称为 “自然染色”。  自然染色法 间隔染色法 例1 给出m,n,k，试用若干1*k的矩形覆盖 m*n的棋盘。 定理1：m*n棋盘存在1*k矩形的完全覆盖的 充分必要条件是k|m或k|n。 证明：  充分性是显然的。 用构造法： 当k|n时，每一行用n/k个1*k的矩形恰好完全 覆盖。k|m情况类似。 证明（续）：  必要性： 当n,m均不能被k整除时，设 m=m1*k+r, 0rk n=n1*k+s, 0sk 并约定r=s (否则旋转90°) 证明（续）： 由上面的定理1，可以彻底解决m*n棋盘的 p*q矩形完全覆盖问题 定理2 ：m*n棋盘存在p*q矩形的完全覆盖充 分必要条件是m,n满足下列条件之一：  （1） p|x且q|y  （2） p|x,q|x,且存在自然数a,b，使y=ap+bq 其中{x,y}={m,n} 定理二证明：  充分性：  若条件(i)满足，不妨设x=m ，y=n ，令m=ps，n=qt, 则m*n的棋盘可以划分为s*t个p*q矩形，结论成立； 若条件(ii)满足，不妨设x=m ，y=n ，即p|m，q|m, 且存在自然数a 、b使得n=ap+bq。那么，将m*n的 棋盘划分为两个棋盘：一个m*ap棋盘，一个m*bq 棋盘，这两个棋盘均可以被p*q矩形完全覆盖，所 以结论成立。 证明（续）  必要性：  设m*n的棋盘可被p*q矩形完全覆盖，从而m*n棋盘 存在1*p矩形的完全覆盖，由定理一知p|m 或p|n， 同理q|m 或q|n ，这有以下两种情况：  (1)p,q可以分别整除m,n 中的各一个，即有p|x,q|y 且{x,y}={m,n} ，则结论成立；  (2)p,q 只能同时整除m,n 中的同一个，不妨设 p|m,q|m。考察至少盖住第一行中一个格的那些覆 盖形，设其中以p*q方式覆盖的矩形有b块，以 q*p方式覆盖的矩形有a块，再注意到第一行共有n 个格，所以n=ap+bq ，结论成立。 例2 设有m*n的棋盘，当m*n为奇数时，尝试 删去一个格子，剩下部分用若干1*2的矩形 覆盖；当m*n为偶数时，尝试删去两个格子， 剩下部分用若干1*2的矩形覆盖。 先来考虑m*n为奇数的情况： 首先将棋盘自然染色， 白色为奇格，黑色为偶格。 无论怎么放，一个1*2的 矩形必盖住一个黑格和一 个白格，而棋盘上的黑格 比白格多1，于是只能去 掉一个黑格(即偶格) 。  另一方面，设去掉偶格为a(i,j)，用构造法 得到可行解 i,j 同为奇数 i,j 同为偶数 再考虑m*n为偶数的情况： 类似地，由自