馮 笑，王艷青

（石家莊學(xué)院 理學(xué)院，河北 石家莊 050035）

0 引言

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

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

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

本研究創(chuàng)造性地將棋盤的多米諾牌完美覆蓋推廣至阿基米德鋪砌中一類（3.6.3.6）鋪砌棋盤的b-牌完美覆蓋，討論n層擴(kuò)展棋盤的b-牌完美覆蓋的存在性.

1 一些定義

阿基米德鋪砌（3.6.3.6）[6]是由無窮多個(gè)正三角形鋪砌元和正六邊形鋪砌元構(gòu)成的平面鋪砌，且每個(gè)頂點(diǎn)的頂點(diǎn)特征為（3.6.3.6），如圖 1所示.在本研究中要求阿基米德鋪砌（3.6.3.6）中鋪砌元的邊長為單位長度.

在阿基米德鋪砌中，由有限個(gè)鋪砌元形成的棋盤稱為阿基米德鋪砌棋盤.在阿基米德鋪砌（3.6.3.6）中，以某一鋪砌元為基礎(chǔ)（稱為基礎(chǔ)棋盤,記為B0），設(shè)與基礎(chǔ)棋盤B0相鄰的鋪砌元的并為T0，稱B1=B0∪T0為1層（3.6.3.6）擴(kuò)展棋盤.設(shè)與n-1層（3.6.3.6）擴(kuò)展棋盤相鄰的鋪砌元的并為Tn-1，稱Bn=Bn-1∪Tn-1為n層（3.6.3.6）擴(kuò)展棋盤.

圖1 阿基米德鋪砌（3.6.3.6）

若基礎(chǔ)棋盤B0為正六邊形，稱n層（3.6.3.6）擴(kuò)展棋盤為I型擴(kuò)展棋盤；若基礎(chǔ)棋盤B0為正三角形，稱n層（3.6.3.6）擴(kuò)展棋盤為II型擴(kuò)展棋盤.

不難看出，當(dāng)n為奇數(shù)時(shí)，I型擴(kuò)展棋盤的最外層鋪砌元為正三角形，II型擴(kuò)展棋盤的最外層鋪砌元為正六邊形；當(dāng)n為偶數(shù)時(shí)，I型擴(kuò)展棋盤的最外層鋪砌元為正六邊形，II型擴(kuò)展棋盤的最外層鋪砌元為正三角形.

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

1）任意兩個(gè)b-牌的交或是空集，或是一個(gè)頂點(diǎn)，或是一條邊；

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

2 主要結(jié)論

引理1 當(dāng)n為偶數(shù)時(shí)，若n層I型擴(kuò)展棋盤可以被2-牌完美覆蓋，則n+3層I型擴(kuò)展棋盤亦可以被2-牌完美覆蓋.

證明：當(dāng)n=0時(shí)，I型擴(kuò)展棋盤為基礎(chǔ)棋盤B0，顯然B0能被2-牌完美覆蓋，下證3層I型擴(kuò)展棋盤可被2-牌完美覆蓋.

首先對該棋盤最外層的正三角形鋪砌元進(jìn)行2-牌覆蓋，如圖3（a）所示.不難看出，除基礎(chǔ)棋盤B0外，棋盤剩余部分同樣可被2-牌覆蓋，因此3層I型擴(kuò)展棋盤可被2-牌完美覆蓋.

當(dāng)n≥2時(shí)，設(shè)n層I型擴(kuò)展棋盤Bn可以被2-牌完美覆蓋，現(xiàn)考慮n+3層I型擴(kuò)展棋盤中，除Bn外的棋盤部分的2-牌覆蓋方法.同樣，首先對最外層，即第n+3層的正三角形鋪砌元進(jìn)行2-牌覆蓋，如圖3（b）和（c）所示，之后對第n+2，n+1層的鋪砌元進(jìn)行2-牌覆蓋，從而得到n+3層I型擴(kuò)展棋盤的2-牌完美覆蓋.

即證.

定理2 n層I型擴(kuò)展棋盤可以被2-牌完美覆蓋；n層II型擴(kuò)展棋盤不存在2-牌完美覆蓋.

證明：設(shè)Bn為n層（3.6.3.6）擴(kuò)展棋盤.

情形1：Bn為I型擴(kuò)展棋盤

圖2 b-牌

圖3 構(gòu)造I型擴(kuò)展棋盤的完美覆蓋

對n進(jìn)行數(shù)學(xué)歸納.n=1時(shí)，B1顯然可以被2-牌完美覆蓋.

假設(shè)Bn-1可以被2-牌完美覆蓋.

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

情形2：Bn為II型擴(kuò)展棋盤

此時(shí)，設(shè)n層（3.6.3.6）擴(kuò)展棋盤中正三角形鋪砌元的個(gè)數(shù)為S.不難看出，當(dāng)n為奇數(shù)時(shí)，n層（3.6.3.6）擴(kuò)展棋盤與n-1層（3.6.3.6）擴(kuò)展棋盤中正三角形鋪砌元的個(gè)數(shù)相等，且S=1+6（2+4+6+…+n-1）≡1（mod2），因此，n層（3.6.3.6）擴(kuò)展棋盤不存在2-牌完美覆蓋.

綜上所述，定理2得證.

定理3 n層（3.6.3.6）擴(kuò)展棋盤不存在b-牌完美覆蓋，b≥4.

證明：b-牌覆蓋的方向有3種，分別記為水平方向、π/3方向與2π/3方向.對n層（3.6.3.6）擴(kuò)展棋盤從最外層開始進(jìn)行b-牌覆蓋，b≥4.不難看出，棋盤最外層鋪砌元的b-牌覆蓋方向只能為π/3方向與2π/3方向.

當(dāng)n層（3.6.3.6）擴(kuò)展棋盤最外層鋪砌元為正三角形時(shí)，若對棋盤最外層最上面左（右）起第一個(gè)三角形鋪砌元T1進(jìn)行π/3（2π/3）方向的b-牌覆蓋，則以T1的左（右）頂點(diǎn)為公共頂點(diǎn)的正三角形鋪砌元總是不能被b-牌覆蓋，如圖4（a）所示（以II型擴(kuò)展棋盤為例），此時(shí)n層（3.6.3.6）擴(kuò)展棋盤不能被b-牌完美覆蓋.

若對棋盤最外層的三角形鋪砌元同時(shí)進(jìn)行π/3方向與2π/3方向的b-牌覆蓋，由棋盤的對稱性，不妨從最上面右起第1個(gè)三角形鋪砌元開始進(jìn)行π/3方向的b-牌覆蓋，第2個(gè)三角形鋪砌元進(jìn)行2π/3方向的b-牌覆蓋，如圖4（b）所示（以II型擴(kuò)展棋盤為例），則總會存在一個(gè)正三角形鋪砌元不能被b-牌覆蓋，此時(shí)n層（3.6.3.6）擴(kuò)展棋盤也不能被b-牌完美覆蓋.

圖4 不存在II型擴(kuò)展棋盤的b-牌完美覆蓋，b≥4

同理，當(dāng)n層（3.6.3.6）擴(kuò)展棋盤最外層鋪砌元為正六邊形時(shí)，不難看出，無論對最外層怎么進(jìn)行b-牌覆蓋，該棋盤均會出現(xiàn)一個(gè)3-牌狀的區(qū)域無法用b-牌覆蓋，如圖4（c）和（d）所示，從而n層（3.6.3.6）擴(kuò)展棋盤也不能被b-牌完美覆蓋.

綜上所述，b≥4時(shí)，n層（3.6.3.6）擴(kuò)展棋盤不存在b-牌完美覆蓋.

對于n層（3.6.3.6）擴(kuò)展棋盤的3-牌完美覆蓋，由定理3的討論可得推論4.

推論4 若n層（3.6.3.6）擴(kuò)展棋盤最外層鋪砌元為正三角形，則該棋盤不存在3-牌完美覆蓋.

當(dāng)n層（3.6.3.6）擴(kuò)展棋盤最外層鋪砌元為正六邊形時(shí)，可得定理5.

定理5 當(dāng)n為奇數(shù)時(shí)，II型擴(kuò)展棋盤不存在3-牌完美覆蓋.

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

3 進(jìn)一步研究的問題

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

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

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