パズルの国のアリス

六角形タイルの悪夢(解答)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 ウォーミングアップ問題は少々易しすぎたようだ。1辺nの三角形領域の面積は,六角形の個数に換算すれば,いわゆる三角数nn+1)/2になる。これが3の倍数になるには,nまたはn+1が3の倍数でなければならないので,もちろんn≡0(mod 3)またはn≡2(mod 3)である。

 さて,以降の問題は,元の形のままで考えることも可能だが,タイル貼りの方法を示すにも,タイル貼りが不可能なことを証明するにも,各六角形を菱形に変形してしまったほうがわかりやすいように思う。まず,タイルが貼られる単位六角形からなる三角形状の領域を,菱形からなる次のような下がギザギザした木の形の領域に変形する。

 すると問題は,菱形3枚をつなぎ合わせた図A’のようなタイルとその向きを変えて置いたB’のようなタイルでこの領域を貼るというものと本質的に変わらないことは納得していただけよう。

例えば高さ9の木の形の領域は下図のようにタイル貼りができる。

 さて,この変形が行われた領域とタイルを使って,n≡ 0,2,9,11(mod 12)のときに,高さnの木がタイル貼りできることを示してしまおう。まず2×3の平行四辺形は,どちらの方向に置かれても,A’とB’でタイル貼りできることが下図から明らかである。従って,一般にサイズが2k×3mの平行四辺形領域もタイル貼りできる。

高さ2の木はタイルそのものであるし,高さ9の木がタイル貼りできることは既に示した。従って,高さ11の木も,下の左図のように分割すればタイル貼りができる。また,高さ12の木も下の右図のようにタイル貼りできる。

 あとは簡単だ。12は2と3の公倍数であり,高さ 2,9,11,12の木のタイル貼りはできているのだから,n≡ 0,2,9,11(mod 12)の場合,高さnの木は,高さが2または9または11の木1つと,高さ12の木をいくつかと,あとは両辺に2の倍数と3の倍数をそれぞれ持つ平行四辺形に分割し,分割成分をそれぞれタイル貼りすればよい。この先は読者にお任せすることにしよう。

 難題はn≡ 0,2,9,11(mod 12)以外の場合にはタイル貼りが不可能なことの証明だ。この種の証明によく使われる手法が色の塗り分けというテクニックである。読者は,チェス盤から隅のマス目を2つ取り去った下図左のような領域がドミノ(サイズ 1×2の長方形)型のタイルで貼ることができないという証明をご存知であろうか。そのツボは,例えば,下図右のように市松模様に塗り分けることである。

 こうすると,ドミノタイルは,どういう位置と方向に置いても青いマスと白いマスを1枚ずつ覆うことになる。従って,ドミノタイルで貼られる領域は同数の青マスと白マスから構成されていなければならない。ところが,この領域は青マスのほうが白マスより多いので,ドミノタイルで貼ることはできない。

 ところが,六角形(またはそれを変形した菱形)のこの問題は実にうまく選ばれており,色分け論法ではうまくいかないことが証明されている〔その証明は,コンウェイ(J. H. Conway)とラガリアス(J. C. Lagarias)が1990年に公表した論文”Tiling with Polyominoes and Combinatorial Group Theory”で扱われているが,かなり込み入っているのでここでは詳述しない〕。とはいっても,色分け論法はかなり強力ではある。六角形を一列に並べた直線型タイル E,F,Gの場合でこれを見てみよう。菱形に変形した版で考えると,これは高さnの木を下のような3種類のタイルを貼り合わせて覆うという問題になる。E’は1点でつながったタイルだが,もちろん切り離したりせずに使うということになる。

 さて,この場合,木領域を下図のように上から青,白,赤と交互に色分けしてみよう。

するとタイルE’はどこに置かれようと同じ色の菱形マスを3つ覆うことになる。また,F’やG’は,青,白,赤のマスを1つずつ覆うことになる。ということは,高さnの木がこの3種のタイルで覆われるためには,青,白,赤のマス数をそれぞれbnwnrn とするとbnwnrnmod 3)が成り立たねばならないということだ。n=6の場合,この図からわかるようにbn=5,wn=7,rn=9であり,この関係が成り立たないから,直線型タイルだけでは覆うことができないと言える。では,逆にbnwnrnmod 3)が成り立てば覆えるかというと,残念ながらそうではない。これが色分け論法の限界で,実際n=8,9(mod 9)の場合にbnwnrnmod 3)が成り立つが,実は高さnの木で直線型タイルE’,F’,G’だけで覆えるものはない。

 というわけで,タイルA’,B’を使う場合も,タイルE’,F’,G’を使う場合も,覆えないということの完全な証明には,色分け以上の分別能力を持つ数学的ツールが必要である。そのためにコンウェイたちが考え出した道具が下図のようなグラフである(グラフはこのパターンで平面全体に広がっていると考えられたい)。

 さて,タイルA’とB’の周を反時計回りに巡る路に下図のようなラベルをつけよう。要は右上に向かう場合U,右下に向かう場合Dで,その逆方向に向かう場合は,それぞれU−1D−1である。

 例えばA’の左端の点からスタートするとDUDUD−1D−1U−1U−1の順路となって元に戻る。ここでこの経路に従って,先のグラフ上を辿ってみよう。その際,Uのときはラベルuの黄色い三角形の周囲を反時計回りに進み,Dのときはラベルdの緑の三角形の周囲を反時計回りに進むことにする。また,U−1,D−1では対応する色の三角形の周囲を時計回りに進む。すると,どの点からスタートしても,また同じ点に戻ることが確認できよう。例えばPという点からスタートすると,赤色の矢印を辿ってまたPに戻る。B’の周囲を巡る順路はDDUUD−1U−1D−1U−1であるが,同じようにグラフを辿ると,似たような形の図形を反対回りに辿って元に戻る。

 ここで少し考えればわかるが,タイルA’とB’だけで貼られる領域がある場合,その領域の周囲を巡る順路に従って,同じようにグラフを辿れば,必ず出発点に戻るといえる。例えば,高さ1の木,すなわち1枚の菱形の周囲を巡る順路はDUD−1U−1だが,それに従ってグラフを辿ると出発点には戻らない。一般に高さnの木の周囲を巡る順路は(DUn D−nU−nだ。ただし,(DUnDUの繰り返しn回,D−nD−1の繰り返しn回を意味する。さて,この路をグラフ上で辿ると,n≡1(mod 3)の場合,元の点に戻らないことを確認するのは易しい。

 読者は,ここで「おやっ」と思われるかもしれない。これでは,六角形の数を数えたセイウチの条件となんら変わりがないからだ。しかし,心配は無用だ。実は上のグラフを使った考察には,もっと微妙な不変量が隠されているのだ。それは戻ってくるループがグラフ上の白い六角形を何周するかということである。例えば,先の(Pを出発してPに戻る)A’の周に従う赤色の矢印ループは,その内側の白い六角形を時計回りに1周している。これに1という値を与え,巻き数と呼ぼう。B’の周に従うループを考えると,今度は反時計回りに1周するので,巻き数は−1ということにする。すると,やはり少し考えればわかるが,タイルA’がa枚とタイルB’がb枚で貼られる領域がある場合,その領域の周囲を巡る順路に従ってグラフ上を辿ると元の点に戻るだけではなく,そのループの巻き数は各タイルごとの巻き数の合計,すなわちabとなる。

 高さnの木の周囲について巻き数を調べると,n≡0,2(mod 3)の場合,その値がn/3であることはすぐわかる。よって,それを覆うタイル貼りがあるなら,abn /3が満たされねばならない(xx以上の最小の整数を表す)。例えばn=3の場合,ab=1であるが,abはタイルの総枚数であるから,もちろんabnn+1)/6=2であり,これらを満足する整数解abは存在しない。n=5,6, 8の場合も同様である。この結果は,一般にn≡3,5,6, 8(mod 12)の場合に拡張できる。逆に,n≡0,2,9,11(mod 12)の場合には,実際にタイル貼りができることは最初に示した。実は,このときA’方向に置くタイルとB’方向に置くタイルの枚数は,上の式から定まっており,例えばn=12の場合,ab=4,ab=26だから,a=15,b=11,すなわちA’方向に15枚,B’方向に11枚のタイルを置かねばならないことが,実際に貼り合わせるまでもなくわかる。

 また,タイル E’,F’,G’ だけを使って,高さ1以上の木を貼ることができないことは,それらのタイルの周囲についての巻き数が0であることからわかる。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004),
Mathematical Mind-Benders(2007) P. Winkler。
邦訳は『とっておきの数学パズル』(2011年),『続・とっておきの数学パズル』(2012年),ピーター・ウィンクラー著,坂井公・ 岩沢宏和・小副川健訳,日本評論社。

問題はこちらです