L 形地板砖铺满正方形地面的施工方案有多少?
如上图所示,有一块 8×8 的正方形地面(图2),有2种面积是 4 的 L 形地板砖(图1)。现在要用这些地板砖恰好铺满正方形地面(图3、4),请问:
如果不许切割,有多少种恰好铺满的方案?(图 3 和图 4 是其中的两种方案) 设正方形的边长为$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里没有收录的一个新数列。 KeyTo9_Fans 发表于 2017-5-29 06:43
设正方形的边长为$n$。
当$n$不能被$4$整除时,方案数为$0$;
唯一关联的是 https://oeis.org/A084480
Fans可以继续计算$6xx4n$,$8 xx n$等 还可以计算3*8n,5*8n等形状 我怎么感觉知乎上有这样类似的问题 我比较关注的是 非平凡的填充方案。 即 不是由 更小的矩形填充方案拼接而成。
很可惜,楼主给的两个例子都是 平凡的解。
比如$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$ 六个小的矩形组成
3)的上部分是非平凡的。或者先考虑单用一种砖是否有非平凡解
怎么准确定义平凡解、非平凡解呢? 四格骨牌.属于 多连块 的一种.其中1*2 的叫做多米诺骨牌.
https://zh.wikipedia.org/zh-cn/四格骨牌
KeyTo9_Fans 发表于 2017-5-29 06:43
设正方形的边长为$n$。
考虑过6*6、10*10情形吗?依然是4的倍数。 容易证明需要格子数目是8的倍数
页:
[1]