パズルの国のアリス

隣の芝生を青くするには(問題)

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

 さわやかな風が吹きぬけるトランプ城の中庭を散歩中のアリスの前にチェシャ猫がいつものように忽然と現れた。

 「やあ,ここも花や芝生が綺麗だな。今まで例のモグラ国にいたんだが,あそこは近ごろ造園工事を始めてね」

 読者は,2011年2月号で紹介した無限モグラ国のことをご記憶であろうか? 無限に広がった平面を碁盤の目のように仕切った区画からなる国で,美しい花で特徴付けられた各区画をモグラが1匹ずつ占有している。

 「造園? 何もしなくても美しいのに」とアリス。
 「そうなんだけど,少しは公共のスペースがあっても良いという話になったらしいんだ。キミも知っての通り,あの国は広さは無限だから,一部のモグラが地所を一定方向にずらせば,好きなだけ空地を作ることはできる。とりあえず10×10の区画を空けて更地にした。で,公共スペースだから,あまり特徴的なのも良くないだろうということで,ともかく芝を植えようということになったが,そのための予算があまりない。そこで,芝はもちろん『四角芝』にして,それで最低限の区画だけを覆って,あとは自生して次第に広がるのを待てばよいだろうということになった」

 不思議の国の住人には,これで十分だろうが,アリスや読者にもわかるように説明を補足しよう。『四角芝』とは,モグラ国などに生える奇妙な芝の品種である。1区画を単位として年とともに次第に増殖するが,その仕方に特徴がある。前に生えていた区画には,防除しない限り翌年もまた自生する。また,前に生えていなかった区画は,辺を接して隣合う4区画のうちの2つ以上に生えていた場合に限り,翌年,新しい芽がふきだし増殖する。

 そばで聞いていた勘のいいグリフォン。「なるほど,それで,10×10の区画全体を芝で埋めつくすのに,最初に植える区画の数をなるべく少なくするにはどうすればいいかを相談しに来たというわけか?」と言い,ちょっと考えたあと,「それなら簡単だ。最初は,この図のように対角線上の10区画にだけ植えておけばその対角線が次第に太くなり,10年目には10×10の区画全体が芝で埋まる」(右の図)。

 「やはりそうか。俺もそれはわかったんだが」とチェシャ猫。「でも,モグラの中には懐疑的なのがいて……もっと少ない区画数から始めてもうまくいくかもしれないじゃないかと言うんだ。いろいろ考えてみたところそんな方法は無さそうなんだが」。

 読者には,この場合は最低10区画に芝を植えねばならないこと,もっと一般には,n×nの区画を埋めるのに,最低n区画に芝を植える必要があることを証明していただきたい。

 また,先の対角線植えでは10年目で全体が埋め尽くされた。最終的には全体が埋め尽くされるけれども,それになるべく多くの年数がかかるような最初の植え方の配置を見つけていただきたい。この後者の問題については,筆者も最長年数が何年になるかを知らない。一般にn×nの区画を埋める場合,最初n区画に芝を植える体系的な方法で,全体が埋まるのが,nが偶数なら (n2+2n−4)/ 2年目,nが奇数なら (n2+2n−5)/ 2年目になる方法が存在し,筆者はそれが最長かもしれないと考えている。体系的かどうかを問わず,もっと年数がかかる植え方を探してほしい。あるいは上が最長だという証明を与えてほしい。

解答はこちらです