魔方吧·中文魔方俱乐部

标题: 我也发个“铺瓷砖”的题（9.12更新） [打印本页]

作者: Cielo 时间: 2008-9-11 15:14:04 标题: 我也发个“铺瓷砖”的题（9.12更新）

<P>（呵呵这个是非原创的题，肯定没有金眼睛的题那么难）</P>
<P> </P>
<P>长宽都是23米的房间，用1x1，2x2，3x3（单位都是米）的瓷砖铺满地板，问至少需要多少块1x1的小瓷砖？</P>
<P> </P>
<P>--------------------------------------------------------------------------------------------------------------------------------------</P>
<P> </P>
<P>很快大家就构造出只用一块1x1小瓷砖的拼法了，但能否一块都不用呢？</P>
<P>下面给几个类似的问题，也可以算作一种提示吧</P>
<P> </P>
<P>1、8x8 的地板能否用1块2x2和15块1x4的瓷砖铺满？</P>
<P> </P>
<P>2、8x8 的地板能否用1块2x2和15块T字形瓷砖铺满？（T字形如图□□□）</P>
<P>                                                                                                         □</P>
<P>3、8x8的地板挖掉左上角1x1的小方块后，能否用21块1x3的瓷砖铺满？</P>
<P>     如果不能，那挖去的1x1小方块在什么位置时，能保证剩下的部分能用21块1x3的瓷砖铺满？</P>

[ 本帖最后由 Cielo 于 2008-9-12 19:37 编辑 ]

作者: kexin_xiao 时间: 2008-9-11 15:52:08

坐沙发想！

作者: kexin_xiao 时间: 2008-9-11 15:57:53

<P>开始回答的4，后来知道错了，就是1！<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/sweat.gif" border=0 smilieid="10"> 以后不算了，免的金眼睛又找我算他的难题！<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> </P>

[ 本帖最后由 kexin_xiao 于 2008-9-11 16:28 编辑 ]

作者: ayi2000 时间: 2008-9-11 16:03:18

重新算了，1块

[ 本帖最后由 ayi2000 于 2008-9-11 17:19 编辑 ]

附件: 1.gif (2008-9-11 17:19:21, 2.43 KB) / 下载次数 122
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjUxNjB8NGViNDQ1NTN8MTc2MTQzODc4M3wwfDA%3D

作者: 魔鱼儿 时间: 2008-9-11 16:47:04

这个得坐下来慢慢算啊,呵呵

作者: ming_fei391 时间: 2008-9-11 16:52:38

感觉应该是4块，正确答案时什么？

作者: kexin_xiao 时间: 2008-9-11 17:44:54

4楼的图不错！

作者: noski 时间: 2008-9-11 18:47:35

哈哈，又见风车！

作者: 金眼睛 时间: 2008-9-11 18:57:16 标题: 回复 8# 的帖子

是啊，这年头流行这个，哈哈<BR><BR>4#强啊，不到一小时就做到1了，应该没前进空间了吧？呵呵！

作者: 刚吃完 时间: 2008-9-11 19:04:40

有，大块喇成小块，打死不用1*1

作者: bbshanwei 时间: 2008-9-11 21:45:17

4楼的图搞的不错啊。

作者: rubik-fan 时间: 2008-9-12 02:57:24

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

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

作者: ggglgq 时间: 2008-9-12 08:19:57

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

作者: flwb 时间: 2008-9-12 08:51:10 标题: 回复 13# 的帖子

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

作者: Cielo 时间: 2008-9-12 10:10:16

<P>

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

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

作者: hw294 时间: 2008-9-13 19:08:24

提示: 作者被禁止或删除内容自动屏蔽

作者: zxl0714 时间: 2008-9-13 19:26:21

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

作者: hw294 时间: 2008-9-13 19:45:10

提示: 作者被禁止或删除内容自动屏蔽

作者: zxl0714 时间: 2008-9-13 21:40:40

<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 编辑 ]

作者: 金眼睛 时间: 2008-9-15 11:42:27

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

作者: Cielo 时间: 2008-9-16 18:12:11

原帖由 <i>金眼睛</i> 于 2008-9-15 11:42 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=239687&ptid=13624" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
Cielo，看到了你的更新，来捧个场，呵呵！
 
不过有个问题，更新的几种情况你都验证过么？
 
□              我的思路：如左图所 ...

<br><br>呵呵你的答案全对！不过有更巧妙的方法哦<img smilieid="17" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border="0"><br>----------------------------------------------------------------<br>我来说说我解原题的方法吧：<br>构造只用一块1x1的拼法很简单，利用风车形：即4个11x12的部分围绕中间1x1的即可。而11x12很容易用2x2、3x3铺满。下面证明一块是最少的：<br><br>将地板看做23x23的方格阵，我们把第1行染黑色，第2行染白色……依次交替染色。这样黑格比白格多23个。<br><br>而无论2x2的瓷砖放在什么位置，只能盖住两黑两白；无论3x3的瓷砖放在什么位置，它盖住的黑、白两色格的个数相差3个。<br><br>由于23不能被3整除，所以无法不用1x1的！<br>

作者: 金眼睛 时间: 2008-9-16 19:08:48 标题: 回复 21# 的帖子

哈哈，强，怎么忘了染色原理了呢，

<BR><BR>脑子都想着编程序的事情了，哈哈，这道题编一个高效的求解程序也很有趣，思路很重要，呵呵！<BR><BR>对了，忘了说了，23*23的我也用程序验证过了，确实必须用1*1，不过还是LZ的解释巧妙啊！

作者: penguiji 时间: 2008-9-17 10:18:38

最少一块1*1

作者: penguiji 时间: 2008-9-17 10:21:51

最少一块1*1

作者: penguiji 时间: 2008-9-17 10:28:31

[localimg=334,300]1[/localimg]

作者: 小小手 时间: 2008-12-19 22:35:59 标题: 回复 4# 的帖子

这图看的真明白。高手。

作者: alinit 时间: 2008-12-20 14:04:57

属于超难题，等待解决...

作者: 龚永明魔方 时间: 2011-6-30 07:14:10

两题有解：

附件: pcz.PNG (2011-6-30 07:14:10, 17.89 KB) / 下载次数 76
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTQ4OTkzfDAxZmJiYWJhfDE3NjE0Mzg3ODN8MHww

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

Powered by Discuz! X2