我也发个“铺瓷砖”的题（9.12更新）

bbshanwei

4楼的图搞的不错啊。

rubik-fan

<P>算了一个答案是零块的，但发现自己犯了错误。希望能有人算出是0块的。</P>

[ 本帖最后由 rubik-fan 于 2008-9-12 03:15 编辑 ]

ggglgq

&nbsp;&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp; 不错，最近好象流行拼图游戏呀？能否构造 0 个 1×1 的方案呢？<BR>&nbsp; <BR>试了半天也没试出来。不知能否证明不存在 0 个 1×1 的方案？ <BR>&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp;

flwb

3x3的1块 2x2的130块,但排不出!

Cielo

<P>

原帖由 <I>ggglgq</I> 于 2008-9-12 08:19 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=236919&amp;ptid=13624" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> &nbsp;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp;&nbsp; 不错，最近好象流行拼图游戏呀？能否构造 0 个 1×1 的方案呢？&nbsp; 试了半天也没试出来。不知能否证明不存在 0 个 1×1 的方案？ &nbsp; &nbsp; &nbsp; &amp;nb ...

</P>
<P>&nbsp;</P>
<P>lgq老师说到了关键之处，就是说要么找到一种不用1x1的拼法，要么证明至少需要一块。</P>
<P>对吧里这么多高手来说，其实不是很难的<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/smile.gif" border=0 smilieid="1"> </P>

zxl0714

楼上的 ，2x+3y为什么等于23呢。。。

zxl0714

<P>我说一下我的想法，如果不用1x1的块，那么对于23x23的地板的每一行的3x3的瓷砖的出现次数必然是奇数。这样，我们就先假设存在一种铺设方案，使得每一行的3x3的瓷砖的出现次数是奇数。用a1,a2,a3...ai...a23表示以第i行为最上端的3x3的瓷砖个数。</P><P>这样a1肯定是奇数。</P><P>第2行的3x3瓷砖出现次数为a1+a2，而a1+a2为奇数，则a2为偶数。</P><P>第3行的3x3瓷砖出现次数为a1+a2+a3，a1+a2+a3为奇数，则a3为偶数。</P><P>第3行的3x3瓷砖出现次数为a2+a3+a4，a2+a3+a4为奇数，则a4为奇数.。</P><P>如此下去，我们可以确定：</P><P>a1为奇数
</P><P>a2为偶数
</P><P>a3为偶数
</P><P>a4为奇数
</P><P>...........
</P><P>a19为奇数
</P><P>a20为偶数
</P><P>a21为偶数
</P><P>由于没有以最后两行为最上端的3x3瓷砖，所以第23行的3x3瓷砖出现次数为a21，所以最后一行的3x3瓷砖出现次数为偶数，与假设相矛盾，所以假设不成立。即无法不使用1x1的瓷砖。</P>

[ 本帖最后由 zxl0714 于 2008-9-13 21:43 编辑 ]

金眼睛

<P>Cielo，看到了你的更新，来捧个场，呵呵！</P>
<P>&nbsp;</P>
<P>不过有个问题，更新的几种情况你都验证过么？</P>
<P>&nbsp;</P>
<P>□&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <STRONG>我的思路：</STRONG>如左图所示，由于对称性，特殊块的左上角只要遍历8*8格子左上角的这十个位置，就可以认为代</P>
<P>□□&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 表了所有的情况。</P>
<P>□□■&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <STRONG>计算方法：</STRONG>编程计算，不过暴力破解的计算量太大，我采用了先输入少量初始条件，然后进行试探的方法。</P>
<P>□□□□&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 每种情况的每个位置，运行时间大约为一秒钟。</P>
<P>&nbsp;</P>
<P>通过计算发现，情况1，2均无解，情况3只有那个1*1的小块在如图黑块所在的位置时才有解。</P>
<P>&nbsp;</P>
<P>由于初始条件输入可能有差错，程序也可能有小错误，所以想问LZ是否验证过这些情况，如果1，2，3的其他位置有解，希望提供一个例子，因为有了例子，就可以很快发现程序的错误，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17"> </P>