矩形排版问题求教海星大哥

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棋盘的各个格中填数：第一列的格从上至下依次填1,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得到k-1的数字的个数。
设m=pk+s,n=qk+t，假设s*t<>0，则不妨设0   +---------+------------+
  |         |            |
  |   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，这并不改变该数模k的余，这样得到一个新的数表，记作A。考察数t与t+1在表A中出现的次数。观察上图可以注意到每一条从右上方到左下方的对角线上的数字都相同，我们从左到右给这些对角线标号。显然，在前t条对角线上不出现t+1。又s+t-1t+1)条对角线上也不出现t+1。所以t+1只出现在第t+1条对角线上，即t+1共出现了s-1次。注意到第t条对角线上的数都为t，所以t在表A中至少出现s次。于是t出现的次数多于t+1出现的次数。易知表A中模k余(t mod 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。那么，将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\n,q\n(用符号a\b表示a不整除b)。考察至少盖住第一行中一个格的那些覆盖形，设其中以"p*q"方式覆盖的矩形有b块，以"q*p"方式覆盖的矩形有a块，再注意到第一行共有n个格，所以n=ap+bq，结论成立。
必要性得证。


根据这个条件，你很容易求出最多可排列的小矩形的数目，至于具体的排列方法，可以用回溯法搜索.