照明 (5) - pzdcの雑記

今回は、「照明 (4)」（https://pzdc.hatenablog.com/entry/2022/06/19/175702）で考えた系列の、w=4とw=5の、個別に調べた部分（図１の枠で囲った5つ）について、具体的な内容を書く。

一般の性質：hに対する単調性

今回、必要照明数が、（wを固定した時に）hに対して単調増加であるという重要な性質を確認できた。今回は考察の一部でこの事実を用いるので、先に書いておく。

ある(w, h)で必要照明数がNであるとする（h≥1）。この時に、(w, h-1)の形をN個以下の照明で照らせることを示せばよい。まず、(w, h)の必要照明数がNであることから、N個の照明で(w, h)を照らす方法が少なくとも一つ存在する。そのような解の一つをとってきて、図２のように、左上の一列を削ることを考える。もし、削る列に照明がなければ、そのまま(w, h-1)の解になる。もし、削る列に照明があるならば、削る列にある照明をいったん取り去る。すると、N-1個の照明が(w, h-1)の空間内に存在する形になる。この段階で、もし(w, h-1)空間のすべてのマスが照らされていれば、N-1の解が存在する。一方、もし(w, h-1)空間に照らされないマスが生じているならば、照らされないマスの集合は、図２に示すように、削った列にあった照明と同じ行に並んでいるはずである(マスが1つである場合も含んでいる）。したがって、照らされないマスの内、一番左のマスに照明を置けば、(w, h-1)の形は美術館のルールに反せずにN個の照明で照らすことができる。

以上から、wを固定した時に、必要照明数はhに対して単調増加であることが示された。

この証明は、より一般に、凸なポリオミノに対しても適用できる。すなわち、凸なポリオミノに対する（凸性を保つ）行の挿入（または列の挿入）に対して、必要照明数は単調である。

凸でない場合にこのロジックがどこで壊れるかを考える。中央の列を除くと、左右のポリオミノに属する照明が喧嘩をするようになる場合がある。また、そもそも凸でないと、除きたい列自体が複数の連結成分に分かれている場合がある。「局所的に凸」であり、その性質を保つように変形する場合に限っては、単調性を示すことができそうである。このあたりも掘り下げると理解が深まりそうだ。別の機会に考えたい。

(w, h)=(4, 4)

図４の形は、明らかに5つの照明で照らすことができる。ここでは、照明が5つ以上必要であることを示す。すなわち、4つの照明では照らしきれないことを示す。

図４の2つの青領域は、1つずつ照明を要する。次に、（照明数を4以下にするためには）赤領域にも1つずつの照明を要することを示す。もし左上の赤領域に照明がないとすると、左上の赤領域は外部から照らす必要があるため、白の領域に少なくとも3つ照明が必要である。しかし、これでは照明数の合計が5になってしまう。よって、（照明数を4以下にするためには）左上の赤領域にも1つ照明が必要である。同様にして、右下の赤領域にも一つ照明が必要である。この時点で、青領域と赤領域の合計4領域について、1つずつ照明を置く必要があることがわかった。したがって、（照明数を4以下にするためには）白領域に照明を置くことができない。この時、マスXを照らすことができない。以上から、照明数4の配置は存在しない。

上界と下界が示された。(w, h)=(4, 4)の必要照明数は5になるとわかった。

(w, h)=(4, 5)

照明数6の配置が存在することは自明。必要照明数の下界6を示したい。そのために、5つの照明ではこの形が照らせないことを示せばよい。

先ほどと同じように、図５のAとDの領域には照明が1つずつ入る。次にBの領域に照明が１つ入ることを示したい。Bに照明が入らないとすると、Cの領域に少なくとも3つの照明が必要になる。今回は5つで足りないことの証明なので、この時点で照明を使い切っており、残りの領域には照明を置くことができない状況にある。緑の斜線領域に対して、AとCからは光が届かないため、Dの照明で照らしきる必要があり、これが不可能であることからハタンを示すことができる。よって、全体の照明数を5以下にするためには、Bの領域に1つ照明が必要である。

ここまでで、青と赤の合計4領域に1つずつの照明が入る必要があることがわかった。今は、5つの照明で照らせないことの照明なので、あと1つの照明しか使えない。黄色のマス2つを照らす必要があるため、図６のように照明を配置する必要がある。この照明によって盤面は"ほとんど"分断された。この時、右下の破線で示した領域は、青領域の1つの照明と赤領域の1つの照明で照らしきる必要があるが、不可能である。よってこれもハタンする。

以上から、照明数5ではこの形を照らすことができない。よって、(w, h)=(4, 5)の必要照明数は6である。

(w, h)=(5, 5)

略証（図７を参照）。(w, h)=(5, 5)の必要照明数は6。

(w, h)=(4, 6)

大きく、少し難しくなってきた。プログラムを書けばあっさり計算できそうだが、まだ頭で考えたい気分。

照明数7の自明解が存在する。6つで照らせないことを示す。

まず、青の領域（XとY）に注目する。Xを照らしきるには3つ以上の照明が必要だが、その3つの照明というのは、必ずしもXの中になくても良い（外部から照らしても良い）。より正確に言うと、A_X、B_X、Xの３領域の中に3つ以上の照明が必要である。同様に、A_Y、B_Y、Yの３領域の中にも3つ以上の照明が必要である。このことから、照明数を6以下にするためには、中央の赤領域には照明が入らない。すると、赤領域は外部（A、Bの4領域）から照らすことになる。

ここで、Xについて改めて考える。今は、A_X、B_X、Xの３領域の中にちょうど3つの照明が入っている状況を考えていた。場合分けして考えると、A_XとB_Xに入る照明数の合計は、0または1であることがわかる。Yについても同様である。一方、赤領域を照らすためには2つ以上の照明が必要である。このことから、A、Bの領域については、X側に1つ、Y側に1つの照明が入るとわかる。これら1つずつの照明で赤領域を照らすためには、「平行」な配置で照らさなければならない。よって、照明が入る領域の組み合わせは(A_X、B_Y)か、または(B_X、A_Y)の、いずれかである。(A_X、B_Y)についてはYの側で、(B_X、A_Y)についてはXの側でハタンが起こるため、結局、照明数が6の解は存在しない。