TSC999 发表于 2017-5-28 22:20:33

L 形地板砖铺满正方形地面的施工方案有多少?



如上图所示,有一块 8×8 的正方形地面(图2),有2种面积是 4 的 L 形地板砖(图1)。现在要用这些地板砖恰好铺满正方形地面(图3、4),请问:

如果不许切割,有多少种恰好铺满的方案?(图 3 和图 4 是其中的两种方案)

KeyTo9_Fans 发表于 2017-5-29 06:43:59

设正方形的边长为$n$。

当$n$不能被$4$整除时,方案数为$0$;

当$n$能被$4$整除时,方案数如下:

$n$        方案数
————————
$0$        $1$
$4$        $10$
$8$        $141970$
$12$        $10368560985792$
$16$        $4932541823459775760027146$

$n=16$的方案数太多,我们只能算出这个数除以$2^64$的余数是$11585358357624770058$,除以$(2^64-1)$的余数是$11585358357625037451$,据此推测方案数为$4932541823459775760027146$。

这是一个新数列,oeis.org里没有收录。

如果要提交到oeis,需要提交的内容如下:

Name: Number of tilings of a 4n X 4n square with L tetrominoes
Data: 1, 10, 141970, 10368560985792, 4932541823459775760027146
Offset: 0
Links: TSC999, <a href="http://bbs.emath.ac.cn/thread-9525-1-1.html">A Chinese webpage where the problem came out</a>
Keyword: hard

#####

如果只能使用其中的$1$种砖块,方案数如下:

$n$        方案数
————————
$0$        $1$
$4$        $3$
$8$        $250$
$12$        $806160$
$16$        $116029753268$

这也是oeis.org里没有收录的一个新数列。

mathe 发表于 2017-5-29 09:52:55

KeyTo9_Fans 发表于 2017-5-29 06:43
设正方形的边长为$n$。

当$n$不能被$4$整除时,方案数为$0$;


唯一关联的是 https://oeis.org/A084480
Fans可以继续计算$6xx4n$,$8 xx n$等

mathe 发表于 2017-5-29 10:06:18

还可以计算3*8n,5*8n等形状

mathematica 发表于 2017-5-29 14:50:52

我怎么感觉知乎上有这样类似的问题

wayne 发表于 2017-5-30 17:46:11

我比较关注的是 非平凡的填充方案。 即 不是由 更小的矩形填充方案拼接而成。

很可惜,楼主给的两个例子都是 平凡的解。
比如$3)$,其实是$(2+6)*8 =2*(4+4)+ 6*8=2*4+2*4 + 6*8$ 三个小的矩形组成。
比如$4)$,其实是$(2+2+4)*(4+4) =2*4+2*4 + 2*4+2*4 + 4*4+4*4$ 六个小的矩形组成

zeroieme 发表于 2017-5-30 22:38:58

3)的上部分是非平凡的。或者先考虑单用一种砖是否有非平凡解

怎么准确定义平凡解、非平凡解呢?

wayne 发表于 2017-6-2 13:02:27

四格骨牌.属于 多连块 的一种.其中1*2 的叫做多米诺骨牌.
https://zh.wikipedia.org/zh-cn/四格骨牌

zeroieme 发表于 2017-6-2 20:49:22

KeyTo9_Fans 发表于 2017-5-29 06:43
设正方形的边长为$n$。


考虑过6*6、10*10情形吗?依然是4的倍数。

mathe 发表于 2017-6-3 12:19:12

容易证明需要格子数目是8的倍数
页: [1]
查看完整版本: L 形地板砖铺满正方形地面的施工方案有多少?