照明 (3) - pzdcの雑記

これまでの記事：

照明：https://pzdc.hatenablog.com/entry/2022/06/05/175444
照明 (2)：https://pzdc.hatenablog.com/entry/2022/06/12/172637

今回も相変わらず照明数の話だが、もう少し雑多なことを書く。

助走

ギャップが大きい図形というものに興味がある。そのような図形の候補として、最初に思いついたのは、分岐がある構造（図１）である。

図１の形は、必要照明数が1で、十分照明数が2である。毎回こういう風に言葉で書くのは面倒なので、以降は(1, 2)と書くことにする。この表記は照明数の可動域を表現する（照明の可動域ではなく、照明数の可動域であるところが少し面白い）。この表記があれば、いちいち照明の配置を図示しなくても、言いたいことが伝わるだろう。例えば、図２のように図形の端に表記して明示する。

以降、必要照明数nと十分照明数sの順序対(n, s)をベースに、考察を進めていく。この順序対を、私は単に照明数と呼んでいることがあるので注意されたい。

ギャップの話に戻る。ギャップのある図形として、ループのある形というのも考えられる。

ここから、ざっくりと「分岐があるか、あるいは、ループがあれば、ギャップが大きくなるのではないか」と期待する。後で見るように、残念ながらそう簡単でもなさそうだが、まずはこの周辺から考えていく。

分岐とループの掘り下げ

分岐とループについてもう少し掘り下げていく。

図４のように、面積0の穴が開いたループの場合は、ギャップが開かない。

分岐がある形でギャップがあることから、「分岐を作るように柱を追加する」とギャップが増加するということがわかる。実際に図５の例で増加する（図ではギャップをgと書いている。以降この表記を用いる）。

では、ループがある構造に対する変形はどうか。

法則が見えない印象である。少し見通しが悪い。別の方向から考えよう。

そもそも、ギャップを大きくしたかったのだった。２つのループをつないだパターンを考えてみる（図７）。

ギャップが2の構造を２つ並べるのだから、ギャップは増えてほしい。感覚的には、つながる部分でギャップの増加が若干打消しそうである。実際に確認してみると、増加分がぴったりと打ち消したのか、ギャップはループが１つの場合と同じ値になってしまった。

実は、ループをいくつこの方針でつなげていってもギャップは増えないことがわかる。例えば上の図８のように欲張り方針的に照明を置いていくことを想像すると、「なるべく少ない照明を置く」場合でも「なるべく多くの照明を置く」場合でも一単位あたり3つ照明を置くことになる。欲張り戦略は必ずしも正確な下限・上限を与えないが、今回の例に関して実際にギャップが2であることを示すのは難しくない。

この例から感じることは、ギャップはなにか「増えにくい」性質を持っていそうだ、ということである。増やしたい、という気持ちが強くなる。

井桁戦略

ギャップを増やすにはどうすればよいか考えていた。一つ考えられるのが井桁戦略とでも呼ぶべきものである。

横線と縦線をn本ずつ用意して、お互いを完全に貫くようにする（貫かなくても照明数の上では同じであるが、わかりやすさのため貫く想定で説明している）。すると、照明数は(n, 2n)になる。このため、ギャップ数はnになる。とりあえずギャップ数を増やしていける構造を一つ見つけることができて安心である。

横線がm本、縦線がn本の場合は、照明数は(max(m, n), m+n)になるため、ギャップ数はmin(m, n)になる。なかなか制御しやすそうである。井桁戦略に関してはほかにも考えていることがあるが、まだあまり考えがまとまっていない。いずれ記事にしたい。

L字と一般化されたジグザグ

L字にも興味がある。ここでは、l字トリオミノの定数倍（r倍）の図形を考える。図１０のように、照明数は(r, 2r)になり、ギャップ数はrになる。

L字で一つ興味深いのは、斜めの照明配置が存在して、シフトしていくように照明の数を一つずつ増減していくことができる点である。この時、L字の「カド」の部分に照明が置かれるパターンはなく、なんとなく「削る」ことがしたくなる（図１１）。

削ってみると、階段状の部分（「斜面」と呼ぶことにする）が２つ新たに露出する。左下の斜面をさらに深く削れば、十分照明数を固定したまま必要照明数を増やすことができそうである。すると、この一連の形の本質は、斜面が２つ存在する点であるように思える。これは、「一般化されたジグザグ」と見ることができそうだ（図１２）。

一般化されたジグザグをL字から発想する際に、２つほど気になることがある。１つは、斜面の長さが奇数の場合はどうか？という点である。この話は、今回はいったんおいておく。もう１つは、左下のカドを削る際に、rマス削るまでは必要照明数が増えないという点である。このため、（少なくともこの方針では）十分照明数は必要照明数の2倍より大きくならない。例えば下の図１３のようにしても、照明数3では不足で、4つ目の照明が必要になる。

井桁戦略の場合も、十分照明数は必要照明数の2倍で抑えられていた。どうも、2倍というのが限界になっていそうである。

S字テトロミノと横ずれ断層

L字トリオミノの次に考えたくなるのは、S字テトロミノ。

S字テトロミノでは、ギャップが0になる。少し予想に反する感覚である。r倍の図形でもギャップは0のままである。この現象を説明するのは一見して難しそうだったが、うまい方法を見つけた。

図１５のように、正方形を「横ずれ」させる。この変形で、必要照明数も十分照明数も変化しない。一辺がnの正方形の照明数は(n, n)であるため、横ずれされた正方形の照明数も(n, n)で、したがってギャップは0のままである。前の例に戻って、r倍のS字テトロミノは横ずれされた正方形の一種とみなせるため、照明数は(r, r)となり、ギャップは0と説明できる。

図１５の横ずれ変形では、かろうじて全体が連結であるように変形をしていた。実は、図形の連結性を保つ必要すらないことに気づく（これは、この後で述べる（非正方形）長方形の考察と関連する）。面白い。

先ほどは正方形の場合だったが、（非正方形）長方形だとどうだろう。