方格覆盖问题

lulijie

13楼的想法是正确的，证明很简单。用f(n,m)表示n*m的总覆盖方法总数。
从以下递推公式就马上能看出f(2,m)是fibonacci数列。
f(2,m)=f(2,m-1)+f(2,m-2)

lulijie

f(n,m)为奇数，那么就要求覆盖图形为左右对称且上下对称的覆盖方法数为奇数。
不满足有两个对称轴的覆盖方法都可以用映射的方法得到另一种覆盖方法。

lulijie

n、m中至少有一个偶数，不妨设n为偶数。
若要求f(n,m)为奇数：
根据两个对称轴的覆盖方法数为奇数，那么n必须是4u+2的形式。


---------------------------------
修正一下，上述是讨论n为偶数，m为奇数的情况。

[ 本帖最后由 lulijie 于 2011-5-31 22:10 编辑 ]

lulijie

从我的叙述中，应该是f(8,5)必为偶数。
--------------------------------------------
即：
f(4u,2v+1)必为偶数，而f(4u+2,2v+1)才有可能是奇数。

lulijie

21楼是对的，我的观点是错误的。
以下是我想利用递推方法的一种尝试：
-------------------------------------------------------------------
由于楼主的题目只涉及奇偶，故引入以下函数。n表示上下的行数，m表示左右的列数。
f(n,m)表示总覆盖方法数的奇偶，0表示偶，1表示奇。
g(n,m)表示上下对称的覆盖方法数的奇偶，0表示偶，1表示奇。
h(n,m)表示既上下对称又左右对称的覆盖方法数的奇偶，0表示偶，1表示奇。
那么有：h(n,m)=f(n,m)    h(n,m)=h(m,n)  
f(2,3k)=1
f(2,3k+2)=0
f(2,3k+1)=1
g(2,m)=f(2,m)
----------------------------
h(2u,2v+1)=g(2u,v)

[ 本帖最后由 lulijie 于 2011-5-31 22:47 编辑 ]