パズルの国のアリス

モグラ国芸能団によるモグラ叩き芸(解答)

 読者はペグソリテアというパズルゲームをご存知だろうか? おそらくどなたも子供の頃に一度くらいは遊んだことがあろうかと思う。一番普通の形は,格子点の上に様々な形にペグを配置しておいて,ペグ同士が互いに縦・横方向に飛び越し,飛び越されたペグを取り除いていくことで,目標の配置にするというゲームだ。ペグが飛び越せるのは,自分の隣りにあるペグだけだし,行き先のマスが空いていないと飛び越すことができない。

 ここまで説明すれば,もう読者はお気づきだろう。実は,モグラ叩きのルールは,モグラの位置だけに着目すれば,見た目こそ違って見えても,ペグソリテアとまったく同じ動きなのだ。要は,長方形状に隙間なく配置されたペグをどうすれば1本だけにすることができるかというペグソリテアの問題と同じだ。

 さて,実際に少し考えてみよう。2×nの配置から始めるとn=2のときは,モグラを1匹だけにすることは誰でも簡単にできよう。だが,n=3のときはなかなかうまくいかない。n=4,n=5の場合は,誰でも簡単というわけにはいかないだろうが,いろいろやってみていただきたい。そのうちに成功するはずだ。ところが,n=6ではうまくいかない。同様にn=7,n=8の場合は(簡単ではないかもしれないが)うまくいき,n=9は難しい。ここまでを整理すると,2×nの配置からの場合,nが3の倍数以外だと,モグラ叩きにより,モグラを1匹だけにすることができるが,3の倍数だとできそうもない。

 では,3×nの場合はどうだろうか?n=2の場合は,2×3の縦横を入れ替えただけだからうまくいきそうにない。ところが,読者にも少し試してみていただきたいが,n=3,4,5,…と増やしてもうまくいきそうにないのだ。こうして3×nは駄目だろうという予想になる。

 次に4×4を試していただきたい。これも,簡単というわけにはいかないかもしれないが,うまいやり方がやがて見つかるだろう。この辺で大胆な予想をたててみよう。すなわち「nmのどちらも3の倍数でなく2以上であれば,モグラ叩きでモグラを1匹だけにすることができる。どちらかが3の倍数ならできない」というものだ。

 実はこの予想は正しい。その証明だが,うまくいく場合を証明するのもそれほど易しくはないが,こちらはモグラ叩きの手順を構成すれば済むので,概略のアイデアを示し,細かい部分は読者に補っていただこう。基本的アイデアは,最初の配置の長方形の隅のほうから2×3と1×3という小さいサイズの(モグラのいる)長方形を剥ぎとっていくことだ。これは,無条件にできるわけではないが,1×3の場合,その上下に空マスとモグラがいるマスがあれば上の図Aのようにして可能だ。図で「も」が書いてあるマスがモグラが顔を出していることを示し,空白は空マスを示す。マス目が描いてない箇所は,操作途上で変更を受けることがないのでモグラがいてもいなくてもどちらでもよい。

 長辺方向にモグラのいる補助マスがあれば,2×3マスを剥ぎとることも,例えば下の図Bのようにすればできる。図の最後の段階は,先の1×3マスけずりを縦方向に行えばよい。

 mnが3で割り切れないなら,どんなm×nの配置に対しても,このようにして,モグラが顔を出しているマス目を1×3または2×3単位で減らしていくことで,最終的には1×2,2×2の配置に帰着させることができるのだ。具体的な手順はmnにより微妙に違いがあるので,読者各自で確認されたい。

 もっと難しいのはmnが3の倍数の場合にうまくいかないことの証明だ。先の手順で3マスまたは6マスずつモグラのいるマス目を減らしていっても,モグラのいるマス目の数はいつも3 の倍数だから,1×2,2×2の配置に帰着することはない。しかし,別のうまい叩き方があって,最終的に1匹だけを残すことができないとは限らない。mnが3の倍数のときこれが不可能だということを示すには,例えば次の不変量を使うのが巧妙だ。

 今,mnが3の倍数のとき,うまい手順でモグラ叩きを進めれば1匹だけを残すことができると仮定しよう。そのモグラのいるマス目をAとして,Aのすぐ上の行のマス目すべてに○をつける。また,Aのすぐ左の列のマス目にもすべて○をつける。さらにそれを延長して繰り返し,上下左右とも3行目ごとにすべてのマスに○をつけると,下図のような格子模様になる。

 さらに,元のモグラの配置マスがどうだったかを図の上に青い枠線で描いてみる。例えば6×7の配置だった場合,上のような枠が描かれることになる。ここで重要なのは,この6×7枠が図のどこに描かれようと,枠内の○のついていないマス目の数は偶数個だということだ。それは,6が3の倍数だからであり,一般にはm×nの枠を上のような図中に描くと,mnのどちらかが3の倍数である限り,枠内の○のついていないマス目は必ず偶数個である。

 次にモグラ叩きを考えよう。縦横に連続する3つのマスを先の図のどこから選ぼうと,3つとも○マスか1つだけが○マスかのどちらかだということはすぐに見て取れよう。そのような状況でモグラ叩きを行うことを考えると,次のいずれかが起こる。

・○マスを2つ叩き,もう1つの○マスからモグラが顔を出す。
・○マスと非○マスを1つずつ叩き,もう1つの非○マスからモグラが顔を出す。
・非○マスを2つ叩き,○マスにモグラが顔を出す。

 非○マスに顔を出しているモグラの数がポイントだ。はじめの2つのケースではその数が変化しないし,第3のケースではその数が2減る。いずれにせよ1だけ減るということはない。従って,非○マスに顔を出しているモグラの数の奇偶性が,モグラ叩きに関する不変量になる。最初は偶数匹が非○マスに顔を出していたのだから,モグラ叩きがどう進行してもその数が奇数になることはない。しかるに,最終的にモグラがAのマスだけに残るということはその数が1になるということだから,モグラ叩きを繰り返しても決してその状況は作り出せないことがわかる。

 

問題はこちらです