魔方吧·中文魔方俱乐部

标题: 一个面积覆盖的证明题 [打印本页]

作者: 东莞的8 时间: 2008-10-12 15:30:51 标题: 一个面积覆盖的证明题

设有一个8X8的正方形,左上和右下各去掉一个1X1的方格,现在你手上有31个1X2的盖子,试证明:没有一种方法可以刚好把缺角的正方形完全覆盖.

作者: purple 时间: 2008-10-12 15:50:34

       经典问题啊，以前看到过，这会又有点晕了，又仔细想了想，棋盘涂色是不应该影响放置1X2块的可行性的，所以将棋盘涂成黑百两色，而如图的涂色法，可明显看出白色块比黑色块少两个（因为黑色两个角拿掉了）。而放置一个1X2必然占据一个白色和一个黑色块，由于白色块和黑色块个数不等，所以不可能出现1X2铺满的情况。通过这种着色就可知无解。
      开始的时候钻牛角尖了，老想为什么非要这样着色，为什么不着别的颜色。后来想明白了，只要用一种着色方法说明了不可能不就行了么，其他的着色方案既说明不了可行也说明不了不行，完全没用。

[ 本帖最后由 purple 于 2008-10-12 16:02 编辑 ]

附件: 8X8.jpg (2008-10-12 16:00:41, 17.13 KB) / 下载次数 66
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjczODN8OGM2OTc1N2F8MTczMjU2NTg3N3wwfDA%3D

作者: Atato 时间: 2008-10-12 16:30:00

楼上的想法很好...起码我就没想到这样弄

作者: 乌木 时间: 2008-10-12 17:03:53

那么，去掉某一个黑格和某一个白格的话，此题怎么解析？

作者: purple 时间: 2008-10-12 20:02:35

乌木老师的问题提得好啊。在下能力有限，写不出严格证明。
我感觉应该是一定有解，自己随便分析了一下，也不知道对不对，请前辈指正
若黑白两格在一条线上（同行或同列），显然有解
若两格不在一条线上，可以这两格为顶点构建出一个矩形，在8X8这个棋盘上，除了构建的矩形之外的部分一定可以用1X2填充，似乎行列数的奇偶特点可以证明这个。然后就变成了一个缺两个对角的非正方形的矩形用1X2填充的问题，这里没想太明白，但直觉似乎有解。

作者: zxl0714 时间: 2008-10-12 21:09:46

这个可以编程解，先按2楼那样染色，这样把每个黑格和周围的4个白格连边，这样这个棋盘就变成了一个二分图，就可以用二分匹配来计算这个二分图有没有完全匹配。这是一道程序竞赛的题，以前听别人说什么情况都可以用数学方法解，好像是分析一个角啥的。。。反正那个人也是听说的，也不会。。。

作者: 东莞的8 时间: 2008-10-12 21:14:38 标题: 回复 4# 的帖子

试着解一下乌木前辈的那个问题。如有不正确的请指出来。写得有些乱，将就看<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/titter.gif" border=0 smilieid="9"> 在8X8的的棋盘图案里,任去掉一黑一白都是可以完全盖住的. 设先选取一黑格去掉,然后再任意去一个白格.作一个刚好能包括这两个格的矩形.为了好表达,我设黑色在左上,白色在右下,(如果反过来则可以看作把整个图案反过来看就行了).由于黑白是相隔开的,所以必有一条边是偶数长度的(这个稍后证明,暂叫引1),暂设矩形长为偶数(如果是高为偶数则等于把图形转90度看),明显这个矩形除了第一列和最后一列的单元格外,中间的都可以用1X2的盖子覆盖,所以可以去掉,所选的矩形变成一个2行N(N小于或等于8)的矩形.左上右下各缺一块.由于左上是黑块,右下是白块,第二列的颜色分布必为:  (白黑)……白。最后一个为白且必为奇数,所以右列是可以用1X2的盖子盖住的，左则同理。所以所作的矩形是可以用1X2的盖子完全盖住的。 剩下的方格这样处理:矩形的两个侧边(宽)延长可把整个划分成五个部分,左右两部分因为棋盘高为8,所以必定可以刚好盖完.由于所作的内矩形有一边为偶数,所以所作矩形的上面和下面两个矩形也有一条偶数的边,所以也是能刚好盖完.
 引1:设有某一个按上方法作出的矩形长和宽都是奇数。左上为黑，右下为白，棋盘的图案相邻的颜色都不相同，所以右下的白色水平移动到黑色的正下方（或正上方）时移动了偶数步，这个格应该为白色，黑色竖直移动到白色的正右方（或正左方）也需要移动偶数步，这时这个格应该为黑色，矛盾，所以引1题设不成立。

[ 本帖最后由 taiabobo 于 2008-10-12 21:16 编辑 ]

作者: Cielo 时间: 2008-10-12 22:46:51

呵呵，我这个帖子里也有类似的问题的： <h2> </h2><h2>我也发个“铺瓷砖”的题（9.12更新）</h2><a href="http://bbs.mf8-china.com/viewthread.php?tid=13624&extra=page%3D2" target="_blank">http://bbs.mf8-china.com/viewthread.php?tid=13624&extra=page%3D2</a>

作者: sokoban 时间: 2008-10-13 11:28:27

原帖由 zxl0714 于 2008-10-12 21:09 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=266088&ptid=14991" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 这个可以编程解，先按2楼那样染色，这样把每个黑格和周围的4个白格连边，这样这个棋盘就变成了一个二分图，就可以用二分匹配来计算这个二分图有没有完全匹配。这是一道程序竞赛的题，以前听别人说什么情况都可以用数 ...

Hall定理，二部分图G=(A,B)，若对A的每个子集X，X的邻点集N[X]都满足
 
| N[X] |>=|A|，（即邻点集的元素个数大于等于X的个数)
 
则有完备匹配。
 
这个定理用来作理论证明时，比较管用。
 
也就是说，只要说明对任意若干个白格子，与他们相邻的黑格子的数量不少于他们就行了。
 
 

[ 本帖最后由 sokoban 于 2008-10-13 11:46 编辑 ]

作者: kexin_xiao 时间: 2008-10-13 13:10:32

学习了！都是高手啊！

作者: 小波 时间: 2008-10-17 23:14:58

强顶强顶！！！！！！！！大力支持，学术意味太浓厚啦，我喜欢，向大家学习

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