一类阿基米德铺砌棋盘的完美覆盖问题

冯 笑，王艳青

（石家庄学院 理学院，河北 石家庄 050035）

0 引言

组合数学[1]是应用广泛的一门重要数学分支，其历史渊源扎根于数学娱乐和游戏中.随着计算机在社会中的重要影响加剧，近几十年，组合数学发展迅速，广泛应用于社会科学、生物科学、信息论等领域.

棋盘的完美覆盖问题是组合数学的经典问题[1，2]，起源于国际象棋棋盘的多米诺牌覆盖：考虑一张8×8国际象棋棋盘，将全等的1×2多米诺牌覆盖此棋盘，使得每一张牌恰好覆盖棋盘上两个相邻的方格，任意2张多米诺牌均不重叠，且棋盘上所有方格都被覆盖.称这种排列为棋盘被多米诺牌的完美覆盖.棋盘的完美覆盖问题重点考虑覆盖的存在性及覆盖的计数和分类，为计算数学这一学科入门问题的理解和探究提供了思路.近些年来许多数学工作者及爱好者从各自的领域内相继对棋盘的完美覆盖问题展开了一系列的探讨与研究，促进了覆盖问题的探索进展[3-5].

平面铺砌问题[6]是组合几何中广泛应用到建筑、艺术设计等实用领域的重要研究课题，其中表现最为突出的就是具有重要应用价值的阿基米德铺砌.所谓平面铺砌T，是指T={Ti：i∈I}，其中Ti（i∈I）为闭集，满足 R2=∪Ti，且 intTi∩intTj=（i≠j），其中 intTi表示 Ti的内部，也就是说 T 覆盖平面 R2时，既无空隙也不重叠，称Ti（i∈I）为铺砌元.阿基米德铺砌是指平面铺砌中以正多边形为铺砌元生成的各顶点特征相同的边对边铺砌.

本研究创造性地将棋盘的多米诺牌完美覆盖推广至阿基米德铺砌中一类（3.6.3.6）铺砌棋盘的b-牌完美覆盖，讨论n层扩展棋盘的b-牌完美覆盖的存在性.

1 一些定义

阿基米德铺砌（3.6.3.6）[6]是由无穷多个正三角形铺砌元和正六边形铺砌元构成的平面铺砌，且每个顶点的顶点特征为（3.6.3.6），如图 1所示.在本研究中要求阿基米德铺砌（3.6.3.6）中铺砌元的边长为单位长度.

在阿基米德铺砌中，由有限个铺砌元形成的棋盘称为阿基米德铺砌棋盘.在阿基米德铺砌（3.6.3.6）中，以某一铺砌元为基础（称为基础棋盘,记为B0），设与基础棋盘B0相邻的铺砌元的并为T0，称B1=B0∪T0为1层（3.6.3.6）扩展棋盘.设与n-1层（3.6.3.6）扩展棋盘相邻的铺砌元的并为Tn-1，称Bn=Bn-1∪Tn-1为n层（3.6.3.6）扩展棋盘.

图1 阿基米德铺砌（3.6.3.6）

若基础棋盘B0为正六边形，称n层（3.6.3.6）扩展棋盘为I型扩展棋盘；若基础棋盘B0为正三角形，称n层（3.6.3.6）扩展棋盘为II型扩展棋盘.

不难看出，当n为奇数时，I型扩展棋盘的最外层铺砌元为正三角形，II型扩展棋盘的最外层铺砌元为正六边形；当n为偶数时，I型扩展棋盘的最外层铺砌元为正六边形，II型扩展棋盘的最外层铺砌元为正三角形.

阿基米德铺砌棋盘的b-牌完美覆盖是指覆盖该棋盘的有限个b-牌构成的集族，满足如下两个条件：

1）任意两个b-牌的交或是空集，或是一个顶点，或是一条边；

2）b-牌的边界仅与棋盘铺砌元的顶点或边相交.

2 主要结论

引理1 当n为偶数时，若n层I型扩展棋盘可以被2-牌完美覆盖，则n+3层I型扩展棋盘亦可以被2-牌完美覆盖.

证明：当n=0时，I型扩展棋盘为基础棋盘B0，显然B0能被2-牌完美覆盖，下证3层I型扩展棋盘可被2-牌完美覆盖.

首先对该棋盘最外层的正三角形铺砌元进行2-牌覆盖，如图3（a）所示.不难看出，除基础棋盘B0外，棋盘剩余部分同样可被2-牌覆盖，因此3层I型扩展棋盘可被2-牌完美覆盖.

当n≥2时，设n层I型扩展棋盘Bn可以被2-牌完美覆盖，现考虑n+3层I型扩展棋盘中，除Bn外的棋盘部分的2-牌覆盖方法.同样，首先对最外层，即第n+3层的正三角形铺砌元进行2-牌覆盖，如图3（b）和（c）所示，之后对第n+2，n+1层的铺砌元进行2-牌覆盖，从而得到n+3层I型扩展棋盘的2-牌完美覆盖.

即证.

定理2 n层I型扩展棋盘可以被2-牌完美覆盖；n层II型扩展棋盘不存在2-牌完美覆盖.

证明：设Bn为n层（3.6.3.6）扩展棋盘.

情形1：Bn为I型扩展棋盘

图2 b-牌

图3 构造I型扩展棋盘的完美覆盖

对n进行数学归纳.n=1时，B1显然可以被2-牌完美覆盖.

假设Bn-1可以被2-牌完美覆盖.

当n-1为奇数时，n为偶数，于是Bn的最外层铺砌元为正六边形，而每个正六边形可以被3个2-牌完美覆盖，因此Bn可以被2-牌完美覆盖；当n-1为偶数时，由引理1可知，Bn+2可以被2-牌完美覆盖.由于B3可被2-牌完美覆盖，n+2与n奇偶性相同，因此Bn可以被2-牌完美覆盖.

情形2：Bn为II型扩展棋盘

此时，设n层（3.6.3.6）扩展棋盘中正三角形铺砌元的个数为S.不难看出，当n为奇数时，n层（3.6.3.6）扩展棋盘与n-1层（3.6.3.6）扩展棋盘中正三角形铺砌元的个数相等，且S=1+6（2+4+6+…+n-1）≡1（mod2），因此，n层（3.6.3.6）扩展棋盘不存在2-牌完美覆盖.

综上所述，定理2得证.

定理3 n层（3.6.3.6）扩展棋盘不存在b-牌完美覆盖，b≥4.

证明：b-牌覆盖的方向有3种，分别记为水平方向、π/3方向与2π/3方向.对n层（3.6.3.6）扩展棋盘从最外层开始进行b-牌覆盖，b≥4.不难看出，棋盘最外层铺砌元的b-牌覆盖方向只能为π/3方向与2π/3方向.

当n层（3.6.3.6）扩展棋盘最外层铺砌元为正三角形时，若对棋盘最外层最上面左（右）起第一个三角形铺砌元T1进行π/3（2π/3）方向的b-牌覆盖，则以T1的左（右）顶点为公共顶点的正三角形铺砌元总是不能被b-牌覆盖，如图4（a）所示（以II型扩展棋盘为例），此时n层（3.6.3.6）扩展棋盘不能被b-牌完美覆盖.

若对棋盘最外层的三角形铺砌元同时进行π/3方向与2π/3方向的b-牌覆盖，由棋盘的对称性，不妨从最上面右起第1个三角形铺砌元开始进行π/3方向的b-牌覆盖，第2个三角形铺砌元进行2π/3方向的b-牌覆盖，如图4（b）所示（以II型扩展棋盘为例），则总会存在一个正三角形铺砌元不能被b-牌覆盖，此时n层（3.6.3.6）扩展棋盘也不能被b-牌完美覆盖.

图4 不存在II型扩展棋盘的b-牌完美覆盖，b≥4

同理，当n层（3.6.3.6）扩展棋盘最外层铺砌元为正六边形时，不难看出，无论对最外层怎么进行b-牌覆盖，该棋盘均会出现一个3-牌状的区域无法用b-牌覆盖，如图4（c）和（d）所示，从而n层（3.6.3.6）扩展棋盘也不能被b-牌完美覆盖.

综上所述，b≥4时，n层（3.6.3.6）扩展棋盘不存在b-牌完美覆盖.

对于n层（3.6.3.6）扩展棋盘的3-牌完美覆盖，由定理3的讨论可得推论4.

推论4 若n层（3.6.3.6）扩展棋盘最外层铺砌元为正三角形，则该棋盘不存在3-牌完美覆盖.

当n层（3.6.3.6）扩展棋盘最外层铺砌元为正六边形时，可得定理5.

定理5 当n为奇数时，II型扩展棋盘不存在3-牌完美覆盖.

证明：由II型扩展棋盘的构造方法可知，当n为奇数时，该棋盘中正三角形铺砌元的个数为S=1+6（2+4+6+…+n-1）≡1（mod3），而正六边形铺砌元恰为两个3-牌的覆盖，因此，II型扩展棋盘不存在3-牌完美覆盖.

3 进一步研究的问题

本研究仅对一类扩展棋盘的b-牌完美覆盖存在性进行讨论，覆盖的计数及分类没有涉及到.今后的研究过程中，主要从以下几个角度加深探究：

1）更一般的（3.6.3.6）棋盘是否存在b-牌完美覆盖？

2）（3.6.3.6）棋盘b-牌完美覆盖的计数及分类.