パズルの国のアリス

隣の芝生を青くするには(解答)

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

 最初の問題は,芝を最低でもn区画に植えておかないとn×nの領域全体が芝で埋まることはないということの証明だが,この種の不可能性を証明する場合の常套手段は,何らかの不変量を考えることだ。つまり,何年たっても変化しない量を考え,目的状態ではその量が初期状態と異なるので,決して目的状態になることがないことを示す。あるいは,変化する量であっても,経年変化は上がるか下がるかの一方向のみだから,初期状態から目的状態には達することがないというのでもよい。

 さて,そのようなうまい量があるだろうか? 実はそれがあるのだ。気がつきにくいが,芝と非芝の境界の全長というのがその不変量である。この量が広義で年々単調に減少することは直感的に明らかだろうが,ここではそのことを敢えて厳密に示しておこう。

 経年変化は,一部の非芝区画が芝区画に変わることだけだから,非芝から芝に変化した区画の外周でその量がどうなっているかを調べればよい。非芝区画は,芝に変わるためには,隣に芝区画が2つ以上なければならないから,その外周での芝との境界全長は最低でも2である。翌年,その区画が芝に変わると,その2つは芝−非芝境界でなくなるので,その外周での境界全長は2以下になる。

 もしn×nの領域が全部芝になったとすると,そのときの境界全長は明らかに4nである。そして,境界全長は広義単調減少なのだから,最初に境界全長が4n以上ない限り,何年待とうとそういう状態にはなりえない。従って,最初に芝を植える区画がn未満ならば,植えた区画がバラバラだったとしても,その境界全長は4n未満だから,芝は決して全体に広がらないことがわかる(ついでながら,植える区画をnで済まそうとすると,それらの区画は互いに隣り合っていてはならない)。

 2番目の問題についての筆者の予想解は次のようなものである。各区画を{1,…,n}×{1,…,n}の座標値で表せば,nが偶数の場合,例えば,1年目には座標
 (1,1),(2,2),(4,4),…,(nn),(1,4),(1,8),…(1,4⌊n/4⌋),(6,1),…,(4⌊(n−2)/4⌋+2,1)
の区画に植えることで,(n2+2n−4)/2年後に全体が芝で覆われる(⌊x⌋はx以下の最大の整数を表す)。また,nが奇数の場合,1年目には
 (1,1),(3,3),…,(nn),(1,5),(1,9),…,(1,4⌊n/4⌋+1),(3,1),(7,1),…(4⌊(n−2)/4⌋+3,1)
の区画に植えることで,(n2+2n−5)/2年後に全体が芝で覆われる。

 n=8とn=7の場合を左下の図に示す。緑色の区画が1年目に植える区画で,それ以外の区画の中に記された数値は,その区画に何年目に芝が生えるかを示す。

 上の初期配置は,各年で増える芝の区画を2以下にして,なるべくゆっくり増殖するように設計してあるが,体系的であるかないかに関わらずもっとゆっくり増殖する植え方があるかもしれない。また,1年目に芝を植える区画を多くすると,普通は早く全体が埋まるような気はするが,それも明らかなことではないから,もっと多く植える配置の中に,全体に広がるのにより多くの年数を要するものがあるかもしれない。そのような配置を見つけたら,ご一報いただけると幸いである。

8月号「隣の芝生を青くするには」の別解

 8月号の四角芝の問題の2問目,「全体が芝で埋まるけれども,それになるべく年数のかかる初期配置を探してほしい」というものに対して,群馬県の高校3年生,大月健史さんからツイッタ−経由で解が寄せられた。また神奈川県の永森修さん,宮崎県の城戸剛さんからも似たようなアイデアに基づく解が送られてきた。いずれも最初にnよりもほんの少し多くの区画に芝を植えるものだ。永森さんの案がわかりやすくて,かつ現状では最長年数を達成しているようだから,それを簡単に説明しよう。

 基本的なアイデアは区画全体を3列ごとに縦に分割して,順次埋めていくことである。縦の各3列を埋めるのに2n−1年かかるので,全体が埋まるまでには,だいたい2n2/3年くらいを要することになり,筆者が予想した年数よりずっと大きい。もう1つの工夫は,最初の何列かが埋まるまでの年数を延ばすことだ。隅のところで緩やかなカーブを描くように配列することで,最初のうちは縦に1列ずつ埋まっていくようにできる。n=9とn=10の場合の永森案は右上のようになる。緑色の部分が最初に植える区画だ。それ以外の区画では何年目に芝が生えるかを中の数値で示す。

 nが一般の場合,左のほうの芝の配置が体系的にできるのかどうかは筆者にはわからない。ただ,各サイズnに対する最長配置は,永森案によれば下の表のようになっており,左のほうの芝の配置を工夫すれば,2n2/3年目を超えられることがわかる。

 これらの年数が最長かどうかわからないが,これ以上に延ばすのは容易ではないだろう。また,最初に芝を植えるのがn区画だけと制限されたらどうなるだろう? こうなると筆者の案が最長だとは思えないのだが。

サイズ 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
年数 23 31 41 53 66 80 96 114 133 153 174 197 222 248 275

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004)
Mathematical Mind-Benders(2007) P. Winkler著

問題はこちらです