魔方吧·中文魔方俱乐部

标题: 方格覆盖问题 [打印本页]

作者: superacid 时间: 2011-5-30 18:26:06 标题: 方格覆盖问题

设m,n是正整数满足2|mn，将m*n的方格表用多米诺(1*2的小方块）覆盖。试给出覆盖方法数为奇数的充分必要条件。

作者: tm__xk 时间: 2011-5-31 05:30:09

推到偶数乘偶数..于是纠结了..-_-||

作者: shaoww 时间: 2011-5-31 11:58:57

猜测：充要条件是mn/2为奇数。

作者: tm__xk 时间: 2011-5-31 13:13:14 标题: 回复 3# 的帖子

不对.
2*5就是反例.

作者: 暴力打开 时间: 2011-5-31 13:31:20

这题很有难度...大家慢慢想

作者: shaoww 时间: 2011-5-31 14:26:58

原帖由 tm__xk 于 2011-5-31 13:13 发表
不对.
2*5就是反例.

即便是2*5，也不是一眼就能看出有多少种覆盖方法呀，是不是我们对题目意思理解有偏差？

作者: tm__xk 时间: 2011-5-31 15:04:58 标题: 回复 6# 的帖子

首先,就算穷举也用不了几秒钟.
其次,反例不一定都必须是一眼看出的,像2*11,2*17,2*23神马的都是反例.
第三,不明白你提的问题从哪儿冒出来的.

作者: shaoww 时间: 2011-5-31 16:11:14

原帖由 tm__xk 于 2011-5-31 15:04 发表
首先,就算穷举也用不了几秒钟.
其次,反例不一定都必须是一眼看出的,像2*11,2*17,2*23神马的都是反例.
第三,不明白你提的问题从哪儿冒出来的.

这样吧，你用穷举法用不了几秒钟，那就例举出来看看呗，只例2*5就可以了，然后说明你的覆盖方法有几种，再可能的话，做出2*(2n+1)覆盖方法通项公式或者递推公式（其中2*3覆盖方法为3种）。

作者: superacid 时间: 2011-5-31 16:30:12 标题: 回复 8# 的帖子

自己做错了还好意思要求别人解释...
2*N的方法数是很容易算出来的，请自己尝试一下

作者: tm__xk 时间: 2011-5-31 19:30:31 标题: 回复 8# 的帖子

9L+1.

字数.

作者: tm__xk 时间: 2011-5-31 19:36:35 标题: 回复 8# 的帖子

这样吧，我用穷举法用不了几秒钟，那你也例举出来看看呗，只例2*5就可以了，然后说明覆盖方法有几种，再可能的话，试做出2*(2n+1)覆盖方法通项公式或者递推公式（其中2*3覆盖方法为3种）。

很简单的.比打一堆字简单多了.

作者: 葙對。。★ 时间: 2011-5-31 19:47:04

数学表示看不懂啊

作者: 骰迷 时间: 2011-5-31 20:06:32

我记得m=2的好像是fibonacci数列
本来打算编程做一些表格出来可是想了一整天没什么好思路

作者: lulijie 时间: 2011-5-31 20:19:32

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

作者: 骰迷 时间: 2011-5-31 20:26:40

又是fibonacci...跟那个'木木木木木'帖子一样
假设加两块到右边，两种情况：
这两块连在一起；
这两块各自跟左边的连一起。于是
f(2,m)=f(2,m-1)+f(2,m-2)

作者: lulijie 时间: 2011-5-31 20:28:05

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

作者: tm__xk 时间: 2011-5-31 20:30:09

所以就像2l所说..到偶数就纠结了....

作者: lulijie 时间: 2011-5-31 21:01:20

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

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

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

作者: tm__xk 时间: 2011-5-31 21:55:42 标题: 回复 18# 的帖子

还没看出来..
5*8ms是奇数?是我看错了么?

作者: lulijie 时间: 2011-5-31 22:06:22

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

作者: tm__xk 时间: 2011-5-31 22:16:19 标题: 回复 20# 的帖子

我刚才是想说..我ms觉得f(5,8)是奇数..
================
不过发现我又眼花了..其实我想说f(5,4)ms是奇数..

作者: lulijie 时间: 2011-5-31 22:45:05

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 编辑 ]

作者: superacid 时间: 2011-5-31 23:00:39

据说奋战了一个晚上做出来了
明天起来发解答

作者: tm__xk 时间: 2011-5-31 23:02:26 标题: 回复 22# 的帖子

跟我一样..就是对称..有奇数就能降..
就剩偶乘偶..开始纠结..

作者: shaoww 时间: 2011-6-1 08:34:19

天啊，这里讨论的起点连fibonacci数列都只是毫无征兆的一笔带过就可以了，还好后面有人做了提醒，总算明白2*n的解法。谢谢！

作者: superacid 时间: 2011-6-1 12:22:11 标题: 解答如下

见附件

附件: 覆盖的奇偶性问题.pdf (2011-6-1 12:22:11, 144.42 KB) / 下载次数 20
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ1OTg2fDdiNDM3NGIzfDE3NDA4NTQ3NTF8MHww

作者: 骰迷 时间: 2011-6-1 18:05:22

我弱弱的解释一下
eg1
f(13,18)
=f(6*2+1,18)
=f(6,18)--定理4
=f(3*2,9*2)
=0--定理9
eg2
f(4,16)
=f(4,(5*2+2)+4)
=1--定理8

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)