パズルの国のアリス

モグラ国芸能団と白の騎士のコラボ(解答)

初期配置図ごとに考えていくよりは,ハンマーヘッドの形に着目して調べていくほうが簡単なようだ。

 その場合,一番扱いやすいのは,実は,Lトロミノ形のヘッドだ。なぜなら,この形は方向を変えて使うことにより,2×2領域内のどの1マスも(他のマスの状況を変化させずに)単独で反転させることができるからだ。例えば,下図の矢印の左のように3回使うと,矢印の右に示した2×2領域の青いマスだけが反転する。

これは,方向さえ変えれば,2×2領域のどのマスに対しても有効だ。こうしてLトロミノ形のヘッドの場合,モグラ叩き領域が2×2以上のマス目なら,どんな初期配置であっても,1匹ずつモグラを処理していくことで,全モグラを地面の下に隠すことができる。

 次に簡単なのは1×2形のヘッドだ。この場合は,初期配置によっては全モグラを地面の下に隠すことができない。少し考えればわかるように,このヘッドで叩いて状態を変えられるマス目は常に2つだから,最初に顔を出しているモグラが奇数匹であれば,何回叩いても,それが奇数匹という状況は変わらない。当然,顔を出しているモグラが0匹という状況は作り出せない。反対に顔を出しているモグラが偶数匹ならば,うまくやればモグラを2匹ずつ対にして消していくことができる。その2匹のマス目がどんなに離れていようと,隣り合ったマス目を次々と叩いていくことで,その2マスを隣りどうしにすることができるからだ。こうして偶数匹が顔を出しているような初期配置ならば,全モグラを地面下に隠すことができる。つまり,問題で与えられた初期配置の中では,左から3番目のものだけが,1×2形のヘッドを持つハンマーで目標達成が不可能ということになる。もちろん,このように奇数匹が顔を出しているような初期配置であっても,どこか1マスの初期状況を変えることで,目標達成が可能な図になる。

 次は2×2形のヘッドを考えよう。いささか厄介になるが,基本的な考え方は1×2形の場合に似ている。気がつくべきことは,この形のヘッドで叩くことでは,領域のどの縦列やどの横列をとっても,そこに顔を出しているモグラの数の奇偶性が変わらないということだ。つまり,顔を出しているモグラが奇数匹いるような列が縦横どちらかの方向に存在すれば,その列のモグラ数がゼロになることはない。一方,どの横列と縦列をとっても,顔を出しているモグラが偶数匹であるような初期配置なら,2×2形のヘッドを持つハンマーを用いて目標が達成できることが証明できる。この証明は少し面倒だが,読者にお任せしよう。ポイントは,ハンマーで叩くことで,上の性質を変えないまま,顔を出しているモグラがいる範囲を次第に狭めていけることだ。こうして,問題の図では,一番左の図以外はいずれもモグラが1匹だけ顔を出している列があるので,目標達成が不可能とわかる。また,1マスの初期状態を反転して奇偶性を変えることができるのは,縦横ともたかだか1列ずつだから,奇数匹のモグラが顔を出している列がたくさんあるような場合,1〜2個のマス目の初期状態を変えても目標を達成できない。

 4つのヘッドの中で一番厄介なのは1×3形のヘッドだろう。簡単のため,モグラが配置されている領域はある程度広いものとしよう。この場合には,領域を下図左のように3色に塗り分けるのが有用だ。ここでは白,赤,青に塗り分けることにし,それぞれ文字W,R,Bで示す。1×3形のヘッドを持つハンマーでは,縦横どちらの方向に叩いても,ヘッドはこの3色のマス目を1つずつ叩くことになる。よって各色のマス目から顔を出しているモグラの数をそれぞれwrbとすると,1回叩くごとにこれらの数の奇偶はすべて入れ替わる。従って,もし何回か叩いた結果,全モグラが地面の下に隠れたなら,wrb=0,つまりすべて偶数になったということだから,初期配置のwrbの奇偶性も一致していなければならない。こうして問題図の左から3番目の初期配置は(wrb)=(3,2,2)で奇偶性が異なっているので,目標は達成できないことがわかる。また,左から2番目の初期配置は(wrb)=(4,0,0)で,どれも偶数だから問題ないようにみえるが,読者もお気づきのように,3色塗り分けは右上がりの対角線だけでなく右下がりの対角線に沿ってもでき,この場合も同じ結論が導かれる。混乱しないように,この塗り分けは黄,緑,紫ですることにし,下図右のようにY,G,Pで示す。各色のマス目に顔を出しているモグラの数をygpとすると,これらの奇偶性も叩くたびに一斉に入れ替わる。左から2番目の初期配置は(ygp)=(2,1,1)で奇偶性が異なっており,目標は達成できない。

 証明は読者に任せることにしたいが,実は,(wrb)がすべて奇数か偶数,かつ(ygp)がすべて奇数か偶数であることが目標が達成できるための必要十分条件だ。よって,問題図の両端の初期配置なら目標が達成できる。 また,領域全体の広さが十分あれば,どんな初期配置であっても,最大2マスの状態を変えることで目標が達成できる。例えば,与えられた初期配置で(wrb)=(奇,奇,偶),(ygp)=(偶,奇,偶)となっている場合,BGマス(上図左ではB,上図右ではGとなっているマス目)を見つけてその状態を反転すれば,(wrb)はすべて奇数,(ygp)はすべて偶数になる。また(wrb)=(奇,奇,偶),(ygp)=(偶,偶,偶)の場合には,WYとRYのマスを1つずつ反転すれば,すべてを偶数にできる。

 ヘッドがテトロミノ形のハンマーも面白いかもしれないが,それを考えるのは読者にお任せしよう。2×2以外のテトロミノには下図のようなものがある。一番左のTテトロミノ形のヘッドを使うことは(領域が十分広ければ)1×2形,つまりドミノヘッドを使うことと同じであることを読者は証明できるだろうか?

問題はこちらです