多米诺牌的完美覆盖问题

yang_bigarm

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

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

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

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


再发一个

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

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

↖____約啶。

看不懂- -``````

Cielo

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

lulijie

楼主的宝很多嘛。
我试试用数学归纳法来证明：
先证  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

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

Cielo

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

ursace

同2楼

yang_bigarm

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

execellent !

oqpwbzxkf

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