L型覆盖

aimisiyou · 发表于 2020-8-7 07:39:27

您需要登录才可以下载或查看，没有账号？欢迎注册

×

8*9网格，能否用18块L型（4个方格）无重叠全覆盖？如果能，共有多少种全覆盖方法？若网格是m*n，除了满足m*n是4的倍数外还应满足什么条件，题目才有解？

mathe · 发表于 2020-8-7 09:31:26

关键是3x8可以如上图填充
另外2x4也可以染色，所以在n*m是8的倍数而且m,n都大于1的情况必然可以成功填充。
但是仅4的倍数是不可以的

mathe · 发表于 2020-8-7 09:33:21

aimisiyou · 发表于 2020-8-7 09:44:59

mathe 发表于 2020-8-7 09:31
关键是3x8可以如上图填充
另外2x4也可以染色，所以在n*m是8的倍数而且m,n都大于1的情况必然可以成功填充 ...

也就是由3*8和2*4两种规格小矩形组合而成的大矩形都可以被完全覆盖。这两种规格是不是最小矩形规格？

aimisiyou · 发表于 2020-8-7 09:50:29

mathe 发表于 2020-8-7 09:33
https://www.cut-the-knot.org/blue/LtilingOfRectangle.shtml

原来如此。感谢提供链接！

aimisiyou · 发表于 2020-10-1 12:08:49

mathe 发表于 2020-8-7 09:31
关键是3x8可以如上图填充
另外2x4也可以染色，所以在n*m是8的倍数而且m,n都大于1的情况必然可以成功填充 ...

对于4*2情形呢？更进一步，对于K*2情形呢？

aimisiyou · 发表于 2020-10-1 22:16:50

手工找到了15*14的一个解，但不知道是不是最小的奇数边长。

aimisiyou · 发表于 2020-10-1 22:33:46

本帖最后由 aimisiyou 于 2020-10-1 22:42 编辑

aimisiyou 发表于 2020-10-1 22:16
手工找到了15*14的一个解，但不知道是不是最小的奇数边长。

偶数边长还能缩小，即15*10的解如图。
绕半天可以由2*5拼凑而来。
是否存在一边长为奇数（非5的倍数）且有解的情况？
如100*23是否有解？

aimisiyou · 发表于 2020-10-1 22:50:55

本帖最后由 aimisiyou 于 2020-10-1 22:55 编辑

aimisiyou 发表于 2020-10-1 22:33
偶数边长还能缩小，即15*10的解如图。
绕半天可以由2*5拼凑而来。
是否存在一边长为奇数（非5的倍数 ...

7*10有解。即可以看成由5*2和7*10组成的都有解。即100*23有解。

aimisiyou · 发表于 2020-10-2 09:09:36

L5*2除了能组合成6*2之外，能否组成一边为奇数？

账号		自动登录	找回密码
密码			欢迎注册

[讨论] L型覆盖