パズルの国のアリス

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

 まずウォーミングアップ問題から考えよう。この種の手順を設計するにはゴールの状態から逆方向に考えていくのが,やりやすいようだ。最終的には左下隅のマス以外にはモグラが姿を消すようにするのだから,その1ステップ前の状態は下図左のようになっているほかはない。「も」のマスがモグラが顔を出しているマスで,空白は空きマスを示す。さらにその前の状態はいくつか考えられるが,なるべく左下が空くようにするなら下図中央が有望そうだ。こうして順次考えていけば,そう難しくもなく(左下の2×2マスが空いた)下図右にたどり着ける。それを初期配置として,考えてきた順を逆にたどれば,モグラを左下隅1匹だけにする手順が得られる。その作業は読者にお任せしよう。

 しかし,これ以上に左下隅の空き領域を広げるのは容易ではない。1ステップ戻すごとに,顔を出しているモグラの数は1匹ずつ増え,図の右上方向に次第に形成されていくモグラマスの厚みが邪魔になるからだ。もう1つや2つなら空きマスを左下に加えることができるかもしれないが,問題の図中央のような8マスからなる空きマスの塊を左下に作ることは実は不可能であり,それを証明するのが本題である。

 この種の証明には,何らかの不変量を見つけるのが数学での常套手段だ。そのアイデアを得るために,すぐ下の図のように,モグラ叩き領域の各マス目に正の整数を割り当てることにしよう。左下隅のマス目を0とし,右または上に行くごとに1ずつ値を増やしていく。

さて,1回のモグラ叩きでは,次のいずれかが起こる。

(1) nのマスの2匹が隠れ, n−1のマスに新たにモグラが顔を出す。
(2) nのマスの2匹が隠れ, n+1のマスに新たにモグラが顔を出す。
(3) n−1のマスと n+1のマスの計2匹が隠れ, nのマスに新たにモグラが顔を出す。

 今,あるモグラ配置において, nのマスにモグラが顔を出しているとき,そのマスの重みを1/2 nと定義し,それらのマスの重みの合計をそのモグラ配置の重みとしよう。

 モグラ叩きが進行するとモグラ配置の重みは変化するが,少し考えればわかるように,上の変化のうち(1)では重みが変わらないが,(2)や(3)では重みは減少する。つまり,モグラ叩きの進行中,モグラ配置の重みは決して増加しない。このことが重要だ。

 目標に達した状態でのモグラ配置の重みはもちろん1/20=1だ。一方,(無限に広がる)全部のマス目にモグラがいる場合のモグラ配置の重みはいくつだろうか? モグラは無限匹いても,配置の重みは無限ではない。最下行の分だけの重みの合計は,よく知られているように

 1+1/2+1/4+…+1/2 n+…=2

だ。同様にその1つ上の行の分の合計は1,さらにその上は1/2と計算していくと,結局,すべての行の合計ということで,全部のマス目にモグラがいる配置の重みは

2+1+1/2+1/4+…+1/2 n+…  =4

ということになる。

 従って,問題の図中央のように左下の8つのマスを空けねばならないとしたら,(無限個ある)他のすべてのマスにモグラが顔を出していたとしても,その配置の重みは

4−(1+1/2+1/2+1/4+1/4+1/4+1/8+1/8)=1

にしかならない。従って,左下の8つのマスを避けた有限配置はどんなものでもその重みは1未満である。一方,目標配置の重みは1であり,モグラ叩きが進行しても重みが増加することはないのだから,左下の8つのマスを避けた配置から目標配置に達することはありえない。

 最後に1×2形のヘッドで叩く場合を検討しよう。この場合,問題の図の中央,8マスを空けた配置から始めても,左下隅に1匹だけを残すことが比較的簡単にできる。例えば左下図から始めればよい。どのようにモグラ叩きを進めるとうまくいくかを確認するのは読者にお任せしよう。左下隅の3×3のエリアを空けることすらできる。

 だが,問題の図右のように左と下の2行ずつを空けたどんな配置からも目標状態に達することはできない。どうしてだろうか? 今度の場合,1回のモグラ叩きでは,次のいずれかが起こる。

(1)n−1のマスとnのマスの計2匹が隠れ,n+1のマスに新たにモグラが顔を出す。
(2)n+1のマスとnのマスの計2匹が隠れ,n−1のマスに新たにモグラが顔を出す。

ここではnのマスにモグラが顔を出しているとき,そのマスの重みをφn と定義しよう。ただし,φ=(1+√5)/2,すなわちφはいわゆる黄金比でφ2φ+1を満たす。また,モグラ配置全体の重みは各マスの重みの合計とする。

 今度もモグラ叩きが進行すると,モグラ配置の重みは変化するが,(1)では重みが減少し,(2)では重みは変わらないことを確認されたい。よって,やはりモグラ叩きの進行中,モグラ配置の重みは決して増加することはない。

 目標に達した状態でのモグラ配置の重みはもちろんφ0=1だ。一方,問題の図右の(左と下の2行を除いた)全部のマス目にモグラがいる場合のモグラ配置の重みはいくつだろうか? 下から3行目の分だけの重みの合計は

だ。同様にその1つ上の行の分の合計はφ−3,さらにその上はφ−4と計算していくと,結局,問題の図右の全部のマス目にモグラがいる配置の重みは

φ−2φ−3+… +φ−n+…=1

ということになる。従って左と下の2行を避けた有限配置はどんなものでもその重みは1未満だから,その状態から目標配置に達することはありえない。

問題はこちらです