パズルの国のアリス

続・色模様反転装置(解答)

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

 最初に5×5の問題は,前号と同じ技法を使って証明できる。まず中央が白い市松模様に転換できないことだが,そのような市松模様上に下の図のようにSマスパターンを貼り付けていくと,赤いSマスが5個になる。

201408-a-img1

 2×2と3×3の装置を使う限り,それをどこで何回使おうと赤いSマスが奇数個になることがないことは先月証明したとおりだから,この模様が生ずることはない。

 次に中央が赤い市松模様だが,例えばSマスパターンを下の図のように貼り付けると赤いSマスは6個である。

201408-a-img2

 Sマスパターンの貼り付け方は他にもあるが,どのパターンをとっても赤いSマスは偶数個になる。それもそのはず,実は中央が赤の市松模様は,2×2と3×3の装置を使って,真っ白な格子模様から作ることができるのだ。

 これを確認するには,先月号で見たように,斜め方向に並んだ3マスだけを反転できることに注意するのがよいようだ。右上がりの方向に,この3マス並び反転を4回行うと下図のパターンが作れることはわかるだろう。これに右下がりの主対角線に沿って3回の3マス変換を行うと中央が赤い市松模様になる。

201408-a-img3

 次は,2×2と3×3に加えて5×5の装置があれば7×7は不要かという問題を考えよう。結論をいうと不要なのだが,7×7の装置がやることを他の3種の装置を組み合わせて真似るよりもっとずっと強い結果を導いてしまおう。それは,3種の装置を使えば,7×7格子上のどのマスであっても,その1マスだけの色を反転させることができるというものだ。

 まず5×5格子の中央のマスだけの色反転ができることに注意しよう。これは簡単で,5×5の装置で全体を反転し,北東と南西の隅で3×3を1回ずつ,北西と南東の2×2を1回ずつ使えばよい。さてそうすると,ずらして考えることで7×7格子上の中央の9マス(下の図の灰色のマス)は,どれも単独で色反転が可能なことがわかる。

201408-a-img4

また,先月の解答で見たように,上下にも左右にも3の倍数だけ隔たった2マスは,その2マスだけを反転させられることがわかっている。ということは,中央の9マスのどれかから上下左右に3の倍数だけ隔たったマスも単独で色反転が可能なことになるが,それは7×7格子上のすべてのマスである。

 結局,49個のマスがどれも単独で反転できるのだから,全部を反転させることもでき,7×7の装置はスピードアップのため以外には不要ということになる。

 ついでに言えば,この1マスごとに反転できるというのは,7×6格子上のマスすべてについてもいえる。その証明は7×7の場合に比べいささか面倒になるが,その延長上にあるので考えていただきたい。また,7×6は,そういうことができる最小サイズで,例えば6×6や5×nの格子ではうまくいかない。なぜなら,それらの格子に下図のようにSマスを配置すれば,2×2,3×3,5×5の装置をどこにおいても,偶数個のSマスが覆われることからわかる。すなわちSマスのどれか1つだけを反転しようとしても,他のSマスが少なくとも1つは必ず一緒に反転してしまう。

201408-a-img5

 最後に3色を扱い順繰りに色替えを行う装置の場合だが,これも2色の場合のSマスと同様に,何らかの不変量を与える仕組みを考えるとよい。それには色より数値で考えたほうが扱いやすいかもしれない。たとえば,3で割ったとき0・1・2余る数値を,それぞれ,赤・青・黄に対応させれば,問題の装置は覆ったマス目の数値をそれぞれ1ずつ増加させるものと考えることができる。6×6格子の模様を自由に変化させられるということは,全部のマス目が0の格子から始めて,各マスの数値を3で割った余りのパターンを好きなように変更できるということである。そこで,たとえば下図のような+と−のパタ-ンを考え,+マスの数値の合計から−マスの合計を引いた数値を計算してみよう。最初は0ばかりなのだから,計算の結果は当然0である。

201408-a-img6

 ここで覆った各マスを1ずつ増加させる装置を使うことを考えてみよう。ちょっと調べると2×2,3×3,5×5のどの装置をどこで使っても,その下に来る+マスの数と−マスの数は同じか3違いだということがわかる。したがって,+マスの数値の合計から−マスの合計を引いた数値は,変化しないか,3増えるか,3減るかのいずれかになる。つまり,その数値を3で割った余りは,これらの変換に対する不変量になり,3で割った余りが変化する+マスや−マスがただ1つだけということはありえないことになる。

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

問題はこちらです