パズルの国のアリス

色模様反転装置(解答)

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

 最初に答えだけを述べるなら,次のようになる。まず,1マスだけ色を反転するのは,そのマスがどこにあろうと不可能である。2マスだけ色を反転するのは,全体が3×4以上で,その2マスが縦にも横にも3の倍数マス分隔たっていれば可能である。そうでなければ不可能だ。また,真っ白な4×4,6×6,8×8の面は市松模様に変えることができるが,4×6の面はそれができない。すでに市松模様に塗られている5×5の色を反転させることもできない。

 このようにある模様を色分けする問題は,数学的な枠組みでとらえれば,有限群の問題と考えることができる。そのように考えることの良さは,類似の問題に共通の理論的視点を与えることで,例えば計算機でしらみ潰しに調べる場合などに無駄や重複を避けるためには有用かもしれない。しかし,個々の具体的問題を解くために役に立つとは限らないので,ここではもっと素朴に考えてみたい。

 不可能性の証明には,群やベクトル空間でなくとも,何か巧妙な数学的道具が必要になりそうだから後回しにしよう。できるという結論を持つ問題は,具体的な手順を与えてやるだけでよい。まず,考えを整理する上で鍵となる3×3の面の対角マス(下図左の緑色のマス)だけの色反転ができることに注意しよう。

201407-a-img1

これは簡単で,3×3の装置で全体を1回,2×2の装置で左下と右上の4マス(上図右の青枠部分)を1回ずつ反転させればよい。図には参考のため各マスが合計何回反転されるかを数字で記しておくが,偶数回の場合はもとに戻ってしまい,奇数を記した対角線マスだけが結局反転されることになる。

 さて,そうすると,3×4の面の2つの3×3部分で対角線マスの反転を対称的に行えば,下図の緑色マスが反転されることになる。最後に下図で青枠で囲った領域を再度反転させれば,左右の上隅のマスだけが反転することになる。

201407-a-img2

この2マスの反転部位を上下左右に平行移動できることは,簡単に納得していただけるだろう。また,90度回転させて考えれば,上下に3隔たった2マスだけを反転させられることもわかる。さらに,この2マス反転を適当につなげていくことで,一般には,上下左右のどちらにも3の倍数分隔たった2つのマスだけを反転させることができる。

 では,白い4×4の面を市松模様に変えられるだろうか。これは例えば次のようにすればよいことがわかる。まず,左下と右上の3×3部分の対角マスを反転する(下図)。

201407-a-img3

市松模様にするには,さらに左下隅と右上隅のマスを反転させねばならないが,これらは上下に3,左右に3隔たっているので,その2マスだけの反転は可能だ。8×8の面は,4×4の面が4枚あると考えて,それぞれを市松模様にすればよい。6×6は,下図を見てもらうのが,わかりやすいかもしれない。

 図でAからIまでの文字を記したマスが2つずつあるが,同じ文字のマスはいずれも上下に3,左右に3隔たっている。したがってそれを対にして,2つずつ反転していけば,市松模様が完成する。

201407-a-img4

 次は,いよいよできないことの証明である。この種の証明には何かの不変量を使うというのが数学では常套手段だ。つまり,騎士の装置による変形を受けても変わらない何かを見つけ,最初の状態と目標とする状態ではそれが異なるから,決して目標状態には行き着くことがないという論法だ。

 その不変量のために下図左のような面を考えよう。面は上下左右に無限に広がっている。文字Sがどのような配置になっているかは図から読み取ってもらえると思う。この配置の妙は,3×3の区画を任意に選ぶとその中に文字Sが必ず4つ含まれるという点だ。

201407-a-img5

 また,2×2の区画を任意に選ぶとその中には,Sはまったく含まれないか,ちょうど2つ含まれる。0も2も4も偶数だということがポイントだ。これが何を意味するかというと,騎士の装置を載せたとき,その下に来るSマスは常に偶数個だから,装置を何回使おうと,色が反転されるマスの数はSマスに限れば常に偶数個だということだ。

 つまり反転したSマス個数の奇偶性が不変量になる。では,1マスだけの反転ができないという証明のために,この不変量を使ってみよう。その場合,反転させたいマスがSと重なるようにn×m面をおく。例えば5×5の中央のマスを反転させたいとしたら,上図右の(A)のようにおく。騎士の装置を使う限り,反転しているSマスは偶数個だから,それが緑色のSマスだけということはありえない。また隣り合った2つのマス目だけを反転させることができないことは,例えば(B)のように長方形をおいてみるとわかる。もし緑色のSマスが反転しているならば,他にもどこか反転しているSマスが存在するはずだからだ。ほかの位置関係にある2つのマスも,それらが上下左右に3の倍数だけ離れているのでなければ,うまく重ねることで,一方をSマス,他方を非Sマスにすることができる。

 また,真っ白な4×6の面を市松模様にできないことは,例えば下図のようにSマス配置と重ねればわかる。図では,赤のSマスが5個あるが,これは奇数なので騎士の装置だけでこの模様は作れない。

201407-a-img6

 最後に,すでに市松模様に塗られている5×5の面を反転させるということは,全部マス目の色を反転させるということだが,下図のようにSマス配置と重ねると,Sマスは11個だから,そのすべてを反転することは不可能だとわかる。

201407-a-img7

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

問題はこちらです