照明 - pzdcの雑記

スマニコリのサービス終了が近づきつつあるということで、久々にスマホの電源を入れて、最近の問題を解いてみていた。

そこでふと気になり始めた問題についてメモ。

図１のように、あと少しで解き終わる、という場面がある（イメージ図なので数字は書いていない）。ここで、残りの空間にいくつ照明を置けるか、また、どのような置き方があるか、という疑問がある。今までは、「なんとなく」2つだろう、という理解だったのだが、モヤモヤするので、もう少し厳密に考えてみたい。

今回も、まずは簡単な状況から考える。

柱なし正方形

柱がない場合の方が見通しが良さそうだ（２重の意味で）。3x3では、明らかに3つの照明を要する。

問題を明確にしておく。今回は、与えられた空間に対して、照明の最小の数を考えることにする。ここではこの数を「必要照明数」と呼ぶ。問題の与え方はいわゆる美術館問題と大体同じで、おおらく先行研究が多数存在するところだろうが、今回はあくまで私自身の理解を深めることが目的である。

3x3の必要照明数が3であることは、ほぼ自明である。学部の線形代数でこういうことをやったようにも思うが、忘れてしまったので、改めて証明しておく。上界は解を例示すれば良いだけなので、簡単に与えることができる。上界として3を既に与えたため、下界として3を与えれば良い。この場合、2個の照明では足りないことを示したい。そのためには、照明が2個の場合に、図３のように、「必ず照らされないマスができる」ことを示せば良い。

くどいようだが、証明しておく：照明が2個なので、照明のない行が少なくとも1行存在する。そのような行の内、一番上の行のインデックスをrとする。列についても同じように、照明のない列の一番左の列をcとする。行と列が(r, c)で与えられるマスは、そのマスを照らす照明が存在しない。したがって、照明が2個の場合は照らされないマスが少なくとも1つ存在する。

一般化によって、NxNの正方形では必要照明数がNであることがわかる（N=1, 2, 3, ...）。上界の与え方は、対角線に照明を並べればよい。

柱なし長方形

少し一般化して、柱なし長方形の場合は、必要照明数がmin(M, N)になる。

これも柱なし正方形の場合とおおむね同じように証明できる。上界は図５のように適当なコーナーから斜めに並べていけばよい。

MとNの内の小さい方になる、というのがなんとなく気持ち悪い印象を与える。「気持ち悪い」というのは、「わかったような、わからないような」という消化不良の状態であるということである。こういったモヤモヤを解消するためには、たくさんの例に触れていろいろな側面から理解を深める必要がありそうだ。

長方形に柱が一つ

とりあえず長方形に対する答えはわかったので、いよいよ柱の効果を見ていきたい。まずは柱が１つの場合（図６）。

一見して難しそうである。単純化された問題から考えていく。

長方形のコーナーに柱が一つ：上界

隅に柱を置くことにする。この場合、正方形の場合と（非正方形）長方形の場合で少し事情が異なる。柱を置いた隅の対角の隅から斜めに、順番に照明を置いていくと、正方形の場合は柱にぶつかるが、（非正方形）長方形の場合は柱にぶつからずに辺にぶつかるまで続く。この配置の仕方については、長方形を削っていくような見方もあるだろう（図８）。

この方針による上界は、正方形の場合min(M, N)-1、（非正方形）長方形の場合はmin(M, N)になる。

削っていくような見方は、逆に、帰納法のように拡大していくような見方にもつながる可能性があるが、あくまで上界を与えるだけであると思われる。下界は別途証明が必要そうだ。

下界については後で考えることにする。

長方形に柱が一つ：上界

柱が隅にない場合については少し難しそうだが、周期境界だと思っておなじように斜めに並べていけば照明数がmin(M, N)の配置（または正方形の場合はmin(M, N)-1の配置）が作れる。この配置について、同じ行or列に照明が来ないことと、全てのマスを照らすこと、の２つを確認する。前者については、modで考えればすぐにわかる。後者について、模式図を描いて考えてみる。

図１０の模式図に対して、図１１では、各対角線配置の照明によって「完全に」照らされる領域に色を塗っている。複数の対角線に照らされる領域は、混ざった色で塗っている。どの対角線にも照らされない領域（白い領域）は、今回の場合分けでは見つからない（少し雑な場合分けなのでこういう書き方をしている）。厳密に証明したわけではないが、大丈夫そうだ。

長方形に柱が一つ：下界

下界について、最初の方法で示すことができる。

ここまでをまとめる。

形	柱	必要照明数
MxN (M≤N)	なし	min(M, N)
NxN	1個	N-1
MxN (M<N)	1個	min(M, N)

包含による評価

もう少し手軽に、もしくは直感的に、必要照明数が分からないだろうか。

一つの考え方は、盤面に正方形が含まれるならば、その正方形の一辺の長さが下界になるというものである。もっともらしい主張だが、本当だろうか？

疑問をより一般に述べる：あるポリオミノXが、別のポリオミノYを包含する時、Xの必要照明数はYの必要照明数以上と言えるだろうか。

図１３の例はこの主張を否定する。すなわち、ポリオミノに対する必要照明数は、単調でない性質を持っている。

したがって、包含による評価は一般にはできないが、正方形の場合は、なんとなく、できそうである。この主張を正当化するために新しい考え方を導入する。あるポリオミノについて、ポリオミノの「外」に照明を置いてポリオミノの中を照らすことを許した場合の必要照明数、というのを考えると、この数は単調性を示すようになる。この意味での必要照明数を、「包含必要照明数」と呼ぶことにする。

定義より、任意のポリオミノについて、包含必要照明数は、必要照明数以下である。MxN長方形に対する包含必要照明数がmin(M, N)であることがわかるため、これが下界の評価に使える。MxN長方形は、M<Nの時（包含必要照明数が等しい）MxM正方形を含むため、（非正方形）長方形は考えなくて良い。以上から、この節の最初の主張が正当化される、と思われるが、少し証明が不完全である。包含必要照明数について、照明が同じ行or列にくることを許しているかどうかを明確にする必要がありそうだ。

追記(2022/6/5)：ポリオミノQをなるべく少ない照明で照らすための"最も都合の良い拡大図形"に対する必要照明数を、Qの「土台数」と呼ぶことにすると、ポリオミノQを内包する任意のポリオミノPについて、Pの必要照明数は、Qの土台数以上になる、と言えそうだ。