照明 (6) - pzdcの雑記

前回（https://pzdc.hatenablog.com/entry/2022/06/25/154928）の続き。

図１の、黒枠で示した7か所を、新たに示した（下記の「個別の証明の概略」を参照）。黄色の背景色は、現段階の予想について示すものである（下記「予想」を参照）。

補題：hの2増加に対する1増加下界

ある(w, h+2)で、必要照明数がNであるとする。この時、(w, h)の必要照明数がNよりも小さいことを示す。

仮定より、N個の照明で(w, h+2)空間を照らす配置が少なくとも1つ存在する。そのような配置を一つ選び、そこから(w, h)を照らす配置を構成するのだが、主張を示すためには、照明数を一つ以上減らす必要がある。

小さいhに対するマップは構成済みで、条件を満たしている。そこで、h≥5、かつ、h≥w-2と仮定して良い。図２のように描ける。

緑の領域には、1個か、または、2個の照明が入っているはずである。1個だと仮定すると、バツ印のマスに照明が入り、すぐにわかるように、N-1個の照明で(w, h)を照らすことができる。2個の場合で、赤い点線の枠内に照明が（少なくともひとつ）ある場合は、少し考えると、多くともN-1個の照明で(w, h)が照らせる。そこで、緑の領域の、赤い点線枠以外の部分に2個の照明が入る場合を考えれば良い。

そして、その場合も結局N-1個以下にできる。下の図３で説明する。

青い部分を照らすことだけを考えれば良い。Y₁からY₃までを順番に検査して、照らされていない初めてのマスに照明を入れれば良い。全ての{Y}が照らされていれば、照明は追加しなくて良い。よって、(w, h)はN-1個以下で照らすことができて、目的の主張は証明できた。

個別の証明の概略

(w, h)=(5, 6)と(6, 6)は、(4, 6)と同じ方針で示すことができる（(4, 6)の証明は前回の記事）。

(w, h)=(4, 8)は、必要照明数が7以上8以下であることがわかっている。そこで、7個の解が存在するかどうかを調べる。

図４のように領域分けする。7個の照明の配置を探したい。(X+C)に4個、(Y+A+B)に3個の照明が必要になるため、合計7個にするために、配分が決定する。この時中央のΓ領域に照明が入らないことに注意する。

次にY側について考える。

A+Bに入る合計の照明数について場合分けしていくと、3個でも2個でも0個でもハタンするため、1個入り、さらに調べると、その1個の照明はA領域に入ることがわかる。Yの2個の照明についても調べると、結局、

図５の右下の配置（白丸）になることがわかる。対称性から、左上の配置も確定する（灰色の丸）。中央の黄色の領域が、あと1つの照明では照らせないため、破綻である。

よって、必要照明数は8である。

(w, h)=(4, 9)は、8以上9以下である。図６の通り、照明数8の配置が存在するため、必要照明数は8である。

最初の補題を適用して、(w, h)=(4, 10)の必要照明数は9とわかる。

(w, h)=(4, 11)は、照明数9の配置がある（図７）ため、必要照明数は9である。再び補題を適用して、(w, h)=(4, 12)の必要照明数は10である。

予想

hに対する増え方は、w=2は周期3、w=3は周期6だった。この調子でいけば、w=4は周期9となるのが自然である（あまり強力な根拠ではないが）。

w=4について、13点のhの値を求めた。ここまでの結果から、周期9だと仮定した場合の増え方がわかる。別途与えた上界は、この増え方にぴったりと張り付いていて、それらしい主張であると考えている。

(w, h)の２次元マップ全体でみると、さらに全体の増え方の予想が立つ。最初の図１で、黄色いマスは、縦に２個同じ数が並んでいる領域である。それ以外の（白い）マスは、hの増加に対して1増加している。数字の入力していない領域はあくまで予想だが、これほど単純な構造に対する問題であるため、これくらい規則的であっておかしくない。