一个面积覆盖的证明题

东莞的8

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

purple

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

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

Atato

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

乌木

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

purple

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

zxl0714

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

东莞的8

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

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

Cielo

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

sokoban

<P>

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

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

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

kexin_xiao

学习了！都是高手啊！