パズルの国のアリス

色模様反転装置(問題)

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

 アリスが白の騎士と連れ立って散歩をしていると,赤のポーンの何人かが刷毛を持って忙しそうに作業をしているところに通りかかった。アリスは,不思議の国でスペードの兵士たちが白バラを赤く塗っていたのを思い出して,きょろきょろとあたりを見回したが,バラなどは植わっていない。「何をしてらっしゃるんですか?」ときくと,ポーンの1人が黙って足元を指差した。鏡の国では,地面の多くがチェス盤のように赤白の市松模様に塗り分けられていることが珍しくない。そこも公園の一部なのだが,8×8の正方形の領域が描かれていて,赤白に塗られている。

 「ここも市松模様に塗られていたんだけど,どうも赤の女王陛下のお気に召さないらしく,赤白を全部反転しろっておっしゃるんだ」とそのポーン。「それでおいらたちがかりだされたんだけど,64マスもあると結構大変でね……」。

 白の騎士はそのやり取りを黙って聞いていたが,「ちょっと思いついたことがある」とアリスに告げ,散歩を中断して,そそくさと帰って行った。

 何日かして,アリスが工房を覗いてみると,白騎士は四角い箱のような形の新しい発明品を前に腕組みをしている。アリスを見て,「ちょうど良いところに来た。これから試運転だ」と騎士。床に4×4の白いマス目が描いてある(下図左)。騎士が装置を床に下ろすと,ちょうど2×2のマス目が覆われた。装置の上面にボタンがあり,それを押すと一瞬ウィーンといううなり音が聞こえ,すぐにやんだ。そこで騎士がその装置を持ち上げると,その下にあった4つの面が赤に塗られている(下図中央)。斜めに1マスずらしてその装置を床に下ろし,もう一度同じ操作をすると,その下の赤だったマスは白に,白だったマスは赤に変わった(下図右)。

201407-q-img1

 「わー,すごい」とアリスが歓声を上げると,騎士はまんざらでもない顔で「ま,大したことではないが,これであの作業もずいぶん効率化されるはずじゃ。もっと大きな面にも対応するように3×3マスを反転させる装置も作ったから,組み合わせて使えば,いろんな面に対応できる」。

 アリスはここでふと疑問に思い,「1×1の装置はいらないんですか?」ときくと,騎士は怪訝そうに「1×1?」とオウム返しだ。アリスが,「だって,最初から市松模様に塗ってあるのを反転するだけならその2種類の装置で十分かもしれないですが,こういう最初は白マスだけなんてのを市松模様にするには?」というと,騎士はしばらく考え込んだ挙句,結局「そういうのは刷毛で塗ればよいのじゃ」と一刀両断である。確かに1マスだけなら刷毛で塗っても……とアリスも思わないではないが,ここで読者への問題である。

 騎士の作った2種類の装置だけを使って,n×m格子のどこか1マスの色だけを反転させることができるだろうか? もし可能だとしたら,そのマスは格子面全体のどのような位置にあればよいだろうか? 次には,同じ問題を2マスで考えてほしい。つまり,同じ2種類の装置だけで格子面上のどこか2マスの色だけを反転させることができるだろうか? 可能だとしたら,その2マスの位置関係はどうなっているだろうか? また,騎士の作った装置だけで,真っ白な4×4,4×6,6×6,8×8の格子を市松模様に変えることができるだろうか? すでに市松模様に塗られている5×5の格子の色模様を反転させることができるだろうか?

解答はこちらです