关于用1个X-pentomino和任意数量I-tromino能否平铺矩形的证明请求
关于用1个X-pentomino和任意数量I-tromino能否平铺矩形的证明请求
大家好,我最近卡在了一个矩形平铺问题上,想请教各位前辈:能不能用一个X-pentomino(十字形五格骨牌)加上任意数量的I-tromino(一字形三格骨牌),完全平铺一个矩形?
我自己先做了一些分析:
- 首先从面积条件来看,矩形总面积得满足 $5 + 3k = S$($k$ 是I-tromino的数量),所以我锁定了尺寸为 $3m+1 \times 3n+2$ 的矩形 $R$,这个尺寸的面积模3余2,和 $5$ 模3的结果一致,符合面积要求。
- 之后我用了两种循环3染色的方法(一种是123循环,另一种是321循环)对矩形进行染色分析,得出结论:X-pentomino的中心必须落在第 $3i-2$ 行、第 $3j$ 列的位置。比如在一个8×10的矩形里,所有标记为“3”的格子就是X中心的可能落点(可惜没法附上原图,大家可以自行想象这个分布)。
现在我想证明这种平铺是不可能实现的,但遇到了瓶颈:如果从X-pentomino中去掉一个I-tromino形状的部分,剩下的“残缺区域”(比如去掉中心标记为3的格子上下两个格子后的区域)是可以用I-tromino平铺的,但问题是覆盖那个中心3格子的I-tromino并不是以X的中心为核心的——这种局部的可行方案并不能推广到整个矩形的完整平铺。
有没有大佬能帮我给出这个问题的完整证明?万分感谢!
备注:内容来源于stack exchange,提问作者Haoran Chen
相关产品推荐
相关产品推荐

