パズルの国のアリス

高次元格子国での造園(問題)

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

 アリスが芋虫探偵局に行ってみると,チェシャ猫が来ており,助手役のグリフォンとなにやら議論に夢中だ。

 「あれ,チェシャ猫さん,全身とも,同じ場所にいるなんて珍しいですね」
 「お,キミか。うん,ちゃんと考え事をするとなると,頭と胴体がつながっていないと,今ひとつ血の巡りが悪いようなんだ。いや,この前,無限モグラ国の造園工事の話をしただろう(2012年8月号)。あの件は一応落着したのだが,それを聞きつけて,3次元格子国の連中が同じことをしようと計画して,俺のところに相談が来たんだよ。あの国はどの方向にも立方体がぎっしり敷き詰められた構造をしていて,『立方芝』を植えようというわけだ」

 「3次元格子国? 立方芝?」
 アリスがキョトンとしていると,そばで水煙管をふかしていた芋虫が,少しえらそうな顔で口を挟む。
 「キミのような地面にへばりついている種族には想像がつかないかもしれないが,東西方向,南北方向だけでなく上下方向にも立方体で埋め尽くされた国が,3次元格子国だ。立方芝というのは,その立方体区画全体に生える特殊な植物で,四角芝の3次元版と言ってよいような増殖の仕方をする」
 アリスは「ふん,自分なんかもっと地面近くに……」と言いかけたが,芋虫はいつか羽化することに気がつき,口をつぐんだ。

 「そう,つまりね,前年に生えていた区画は,防除しない限りまた生えるが,前に生えていなかった区画は,隣接する区画の半数以上に生えていた場合に限り,翌年新しい芽が吹き出す。立方体の面は6つだから,つまり隣6区画のうち3区画以上に生えていた場合だ」とグリフォンが補足した。
 「あ,わかったわ。また,空き地をその芝で埋めようというんでしょう。しかも,最初はなるべく少ない区画に植えて,年々増殖させることで全体に広げる」
 「そう,予算が限られているので,どこでも考えることは同じみたいだ」とチェシャ猫。「4×4×4の空き地を埋めるのに,最低で何カ所に植えればよいかというわけさ。四角芝のときと同じで,芝と非芝の境界の面積が不変量になり,それは経年変化では増加することはない。一方,4×4×4の立方体の表面積は4×4×6=96だから,最低でも96/6=16カ所に植えないと全体に広げるのは無理だとはわかるんだけど,こうすればよいという具体的な植え方がなかなかわからない」。

 さて,読者の皆さんには,アリスたちへのアドバイスをお願いしたい。さらに余裕のある読者は,これを一般化した問題,すなわち,最初にn2カ所に植えてn×n×nの立方体に広げる問題はいかがだろうか? さらに余裕があれば,次元も一般化して,サイズndの超立方体に芝を広げる問題に挑戦していただきたい。この場合も芝の増殖条件は同じで,まだ芝の生えていない超立方体に翌年新しい芽が出てくるための必要十分条件は,隣接する2d個の超立方体のうちの半数以上,すなわちd個以上に芝が生えていることである。この場合,最初にnd−1区画にうまく植えれば,全体に広げることができる。

解答はこちらです