荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: huhaiming (一生只爱她), 信区: Program
标 题: 棋盘覆盖 --nju
发信站: 荔园晨风BBS站 (Sun May 11 11:30:38 2003), 转信
// 贴出来的东西，希望大家能看看，提高自己。 都是一些基础性的知识
//更多的论文，大家去oibh下载
m*n的棋盘的p*q矩形完全覆盖的充要条件
我先研究了大矩形可以被小矩形完全覆盖（不留空隙）的充要条件。下面的证明方法如
果有有错，或者有更好的证明方法，请大家不 赐教?
先用数学语言定义几个概念：
m*n的棋盘是指由m行n列方格构成的棋盘。
所谓棋盘的覆盖，是指用若干个相同的图形去覆盖m*n的棋盘，覆盖棋盘的每个图形也由
若父 个方格组成，称之为覆盖形。在棋盘的覆盖中，约定?意两个 哺切位 不相重叠，
且任意一个覆盖形的任何一个方格与棋盘的某个方格重合。
下面先研究简单的情况，当p=1,q=k的情况。
定理一：
m*n的棋盘存在1*k矩形的完全覆盖的充要条件是k|m或者k|n。 （其中a|b表示a整除b）
证：充分性显然。下面证明必要性。
假设m*n的棋盘存在1*k矩形的完全覆盖。在m*n棋盘的各个格中填数：第一列的格从上至
下乙来翁?,2,..m，此外，对于其中的任何一行，所填的各数从左至右构成公差为1的等
差数列。这样，每一个1*k矩形在棋盘的覆盖中所盖住的格所填的数字恰好构成模k的一
个完系（如果一个整数集中?
拿 一个数模k得到的集合是{0,1,...,(k-1)}，则称该集合为模k的完系）。因为m*n的棋
盘在1*k矩形的完全覆盖，所以m*n的棋盘中所填的数字中属于模k的不同剩余类的数的个数
相，也就是说，m*n的棋盘上所填的数字中，所有模k得到0的数字的个数=所有模k得到1的
数字
母鍪?...=?
心得到k-1的数字的个数。
设m=pk+s,n=qk+t，假设s*t<>0，则不妨设0<s<=t<k。将m*n的棋盘分为3块：一个s*t的
矩形
一个pk*n的矩形，一个s*qk的矩形，如下图所示：
+---------+------------+
| | |
| s*t | s*pk |
| | |
+---------+------------+
| |
| pk*n |
| |
+----------------------+
显然，pk*n的矩形和s*pk的矩形可被1*k矩形完全覆盖（由充分性知），所以这两个矩形
中等于模k的不同剩余类中的数的个数相等，从而s*t的矩形中属于模k的不同剩余类中的数
的
个也应该相等。考察s*t的矩形中所填的数字：
1 2 3 .... t-1 t
2 3 4 .... t t+1
............................
s-1 s s+1 .... s+t-3 s+t-2
s s+1 s+2 .... s+t-2 s+t-1
将上述的数表作如下改造：对于表中的每一个数a，如果a>k，则将a换作a-k，这并不改
变该
的余，这样得到一个新的数表，记作A。考察数t与t+1在表A中出现的次数。观察上
图可注意到每一条从右上?到左下方的对角线上的数字都相同，我们从左到右给这些对角线
标。显然，在?
皌条对角线上不出现t+1。又s+t-1<k+t-1<k+t+1,所以在第j(j>t+1)条对角线上也不出现
t+1
所以t+1只出现在第t+1条对角线上，即t+1共出现了s-1次。注意到第t条对角线上的数
都为
，所以t在表A中至少出现s次。于是t出现的次数多于t+1出现的次数。易知表A中模k余(
t mo
k)的数只有t，模k余((t+1) mod k)的数只有t+1，所以A中模k余(t mod k)的数的个数不
等?
模k余((t+1) mod k)的数，即原来的s*t矩形中属于模k的不同剩余类中的数的个数不相
等，
盾。
所以s*t<>0不成立，即s*t=0。必要性得证。
下面利用定理一将结论扩展到m*n的棋盘的p*q矩形完全覆盖。
定理二：m*n的棋盘的p*q矩形完全覆盖的充要条件是m,n满足下列条件之一：
(i) p|x且q|y
(ii)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。
那么
玬*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\n,q\n(用符号a\b表示a不整
除b)
？ 察至少盖住第一行中一个格的那懈 盖形，设其中以"p*q"方式覆盖的矩形有b块，以
"q*
"方式覆盖的矩形有a块，再注意到第一行共有n个格，所以n=ap+bq，结论成立。
必要性得证。
--
※ 修改:·huhaiming 於 May 11 11:38:45 修改本文·[FROM: 192.168.0.200]
※ 转载:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店