魔方吧·中文魔方俱乐部

标题: 多米诺牌的完美覆盖问题 [打印本页]

作者: yang_bigarm 时间: 2009-4-4 23:45:08 标题: 多米诺牌的完美覆盖问题

一个多米诺牌的完美覆盖，指的是由若干个1x2的长方形多米诺牌组成的一个覆盖，这个覆盖恰好盖住了
所指定的区域的每一个格子，同时任何两个1x2的长方形都不重叠。

---------------------------------------------problem 1-------------------------------------------------------

有一个m行，n列的国际象棋棋盘(m,n>0)，m和n都是奇数，容易知道该棋盘的一种颜色的放歌比另一种多一个
（假设是黑色比白色多），证明：如果棋盘上恰有一个黑色方格禁止放东西，那么该棋盘有一个多米诺牌
的完美覆盖。

-------------------------------------------------END-------------------------------------------------------

再发一个

---------------------------------------------problem 2-------------------------------------------------------

有一个m行，n列的国际象棋棋盘(m,n>0)，m和n中至少有一个是偶数，容易知道该棋盘上的黑色格子数跟白色的
一样多。证明：如果棋盘上恰有一个黑格子和一个白格子禁止放东西，那么该棋盘有一个多米诺牌
的完美覆盖。
-------------------------------------------------END-------------------------------------------------------

附件: [一个6x6的棋盘] p1.jpg (2009-4-4 23:45:08, 15.63 KB) / 下载次数 93
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NDQxNzl8YjNkMTVmMTN8MTc0MDc3MjY0NHwwfDA%3D

附件: [对这个棋盘的多米诺牌的完美覆盖] p2.jpg (2009-4-4 23:45:08, 16.38 KB) / 下载次数 82
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NDQxODB8NzU5MzQ3NmN8MTc0MDc3MjY0NHwwfDA%3D

作者: ↖____約啶。 时间: 2009-4-4 23:54:31

看不懂- -``````

作者: Cielo 时间: 2009-4-5 00:07:02

我在《棋盘上的组合数学》一书中见过，不过不太记得解答了

作者: lulijie 时间: 2009-4-5 00:11:52

楼主的宝很多嘛。
我试试用数学归纳法来证明：
先证  m*n m、n都是奇数
1. 3*3  显然存在多米诺牌的完美覆盖
2. 假设m*n  存在多米诺牌的完美覆盖那么
一。 m*(n+2)棋盘，其中  m*n区域根据假设已经存在多米诺牌的完美覆盖，那么第n+1和n+2横行，我们都数竖着放1x2的长方形，显然能把这两行填满。  所以 m*(n+2)棋盘也存在多米诺牌的完美覆盖。
二。(m+2)*n棋盘 ,同理也存在多米诺牌的完美覆盖。
三。(m+2)*(n+2)棋盘 , 在它们角多出的2*2格子，显然可以用两个1x2的长方形填满。
综合上述3个方面，可推出  任何 m*n  （ m、n都是奇数）存在多米诺牌的完美覆盖。
------------------------------------------------------------------------------------------
对于m和n中至少有一个是偶数的情况，照样可以用数学归纳法证明。
1. 1*2 显然存在多米诺牌的完美覆盖.
2. 假设m是偶数，假设m*n  存在多米诺牌的完美覆盖
   一。那么对于 m*（n+1) 棋盘，增加了m*1  的格子，显然能用 m/2 个1x2的长方形填满。
   二。(m+2)*n棋盘，道理同奇数*奇数。
三。 (m+2)*(n+1)棋盘，增加的角上1*2的格子，显然可以用一个1x2的长方形填满
所以对于m和n中至少有一个是偶数的情况，存在多米诺牌的完美覆盖

作者: zxl0714 时间: 2009-4-5 00:19:18

呵呵，其实就是证明这个图存在完备匹配，用hall定理就可以。

作者: Cielo 时间: 2009-4-5 00:22:03

做个广告，我以前发过几个简单的覆盖题：
http://bbs.mf8-china.com/viewthr ... &extra=page%3D5

作者: ursace 时间: 2009-4-7 01:31:13

同2楼

作者: yang_bigarm 时间: 2009-4-7 20:02:17

原帖由 zxl0714 于 2009-4-5 00:19 发表
呵呵，其实就是证明这个图存在完备匹配，用hall定理就可以。

execellent !

作者: oqpwbzxkf 时间: 2009-4-10 10:51:03 标题: ...

每日顶个贴，快乐中国人！

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