一類阿基米德鋪砌棋盤的完美覆蓋問題

馮 笑，王艷青

（石家莊學院 理學院，河北 石家莊 050035）

0 引言

組合數(shù)學[1]是應用廣泛的一門重要數(shù)學分支，其歷史淵源扎根于數(shù)學娛樂和游戲中.隨著計算機在社會中的重要影響加劇，近幾十年，組合數(shù)學發(fā)展迅速，廣泛應用于社會科學、生物科學、信息論等領域.

棋盤的完美覆蓋問題是組合數(shù)學的經典問題[1，2]，起源于國際象棋棋盤的多米諾牌覆蓋：考慮一張8×8國際象棋棋盤，將全等的1×2多米諾牌覆蓋此棋盤，使得每一張牌恰好覆蓋棋盤上兩個相鄰的方格，任意2張多米諾牌均不重疊，且棋盤上所有方格都被覆蓋.稱這種排列為棋盤被多米諾牌的完美覆蓋.棋盤的完美覆蓋問題重點考慮覆蓋的存在性及覆蓋的計數(shù)和分類，為計算數(shù)學這一學科入門問題的理解和探究提供了思路.近些年來許多數(shù)學工作者及愛好者從各自的領域內相繼對棋盤的完美覆蓋問題展開了一系列的探討與研究，促進了覆蓋問題的探索進展[3-5].

平面鋪砌問題[6]是組合幾何中廣泛應用到建筑、藝術設計等實用領域的重要研究課題，其中表現(xiàn)最為突出的就是具有重要應用價值的阿基米德鋪砌.所謂平面鋪砌T，是指T={Ti：i∈I}，其中Ti（i∈I）為閉集，滿足 R2=∪Ti，且 intTi∩intTj=（i≠j），其中 intTi表示 Ti的內部，也就是說 T 覆蓋平面 R2時，既無空隙也不重疊，稱Ti（i∈I）為鋪砌元.阿基米德鋪砌是指平面鋪砌中以正多邊形為鋪砌元生成的各頂點特征相同的邊對邊鋪砌.

本研究創(chuàng)造性地將棋盤的多米諾牌完美覆蓋推廣至阿基米德鋪砌中一類（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為奇數(shù)時，I型擴展棋盤的最外層鋪砌元為正三角形，II型擴展棋盤的最外層鋪砌元為正六邊形；當n為偶數(shù)時，I型擴展棋盤的最外層鋪砌元為正六邊形，II型擴展棋盤的最外層鋪砌元為正三角形.

阿基米德鋪砌棋盤的b-牌完美覆蓋是指覆蓋該棋盤的有限個b-牌構成的集族，滿足如下兩個條件：

1）任意兩個b-牌的交或是空集，或是一個頂點，或是一條邊；

2）b-牌的邊界僅與棋盤鋪砌元的頂點或邊相交.

2 主要結論

引理1 當n為偶數(shù)時，若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-牌完美覆蓋，現(xiàn)考慮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進行數(shù)學歸納.n=1時，B1顯然可以被2-牌完美覆蓋.

假設Bn-1可以被2-牌完美覆蓋.

當n-1為奇數(shù)時，n為偶數(shù)，于是Bn的最外層鋪砌元為正六邊形，而每個正六邊形可以被3個2-牌完美覆蓋，因此Bn可以被2-牌完美覆蓋；當n-1為偶數(shù)時，由引理1可知，Bn+2可以被2-牌完美覆蓋.由于B3可被2-牌完美覆蓋，n+2與n奇偶性相同，因此Bn可以被2-牌完美覆蓋.

情形2：Bn為II型擴展棋盤

此時，設n層（3.6.3.6）擴展棋盤中正三角形鋪砌元的個數(shù)為S.不難看出，當n為奇數(shù)時，n層（3.6.3.6）擴展棋盤與n-1層（3.6.3.6）擴展棋盤中正三角形鋪砌元的個數(shù)相等，且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-牌覆蓋，該棋盤均會出現(xiàn)一個3-牌狀的區(qū)域無法用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為奇數(shù)時，II型擴展棋盤不存在3-牌完美覆蓋.

證明：由II型擴展棋盤的構造方法可知，當n為奇數(shù)時，該棋盤中正三角形鋪砌元的個數(shù)為S=1+6（2+4+6+…+n-1）≡1（mod3），而正六邊形鋪砌元恰為兩個3-牌的覆蓋，因此，II型擴展棋盤不存在3-牌完美覆蓋.

3 進一步研究的問題

本研究僅對一類擴展棋盤的b-牌完美覆蓋存在性進行討論，覆蓋的計數(shù)及分類沒有涉及到.今后的研究過程中，主要從以下幾個角度加深探究：

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

2）（3.6.3.6）棋盤b-牌完美覆蓋的計數(shù)及分類.