前回の記事（https://pzdc.hatenablog.com/entry/2022/06/05/175444）で美術館の照明数の下限（必要照明数）について考えた。
今回は上限（十分照明数）について考えてみる。
用語の定義
今回の記事では次の用語を用いる。
- 必要照明数： 与えられた図形の（美術館のルールに従う）照明数の最小値。
- 土台数： 与えられた図形を包含する図形集合の必要照明数の最小値。
- 十分照明数： 与えられた図形の（美術館のルールに従う）照明数の最大値。
- ギャップ： 十分照明数と必要照明数の差。
与えられた図形に対して具体的な照明配置を与えると、それは必要照明数の上界を与え、同時に十分照明数の下界を与える。必要照明数の下界を与えるには、-1の照明数の時に照らされないマスができることを示せばよかった。十分照明数の上界を与えるには、+1の時に照らしあう照明ができることを示せばよいだろう。
柱がない場合
前回同様、まずは柱がない長方形（正方形を含む）から考える。
3x5の盤面を図１に示している。必要照明数の配置が下界3を与える。
3つある行について、どの行にも最大で1つの照明しか入らないため、合計で最大3つしか照明が入りえない。これから上界数3がわかる。鳩ノ巣原理で説明することもできる。
よって3x5の十分照明数は3である。
容易に一般化ができて、長方形（正方形を含む）の十分照明数はmin(M, N)である。これは必要照明数と等しいため、ギャップは0である。
長方形に柱を一つ：概観
まず、ざっくりと試してみて傾向をつかみたい。
図２に3x5長方形の場合について具体的な配置の例を載せている。配置を作る際は、「なるべく」多くの照明を置くように意識している。
図２の傾向から、次の予想が立つ。
- 柱が短辺上にある場合は、十分照明数はmin(M, N)である。
- 柱が短辺上にない場合は、十分照明数はmin(M, N)+1である。
図２の例は長方形だった。正方形で試しても同じ傾向が見られる。
長方形に柱を一つ：上界
上界の証明は易しい（図３）。
長方形を、長辺方向に分割する（正方形の場合はどちらでも可）。すると、短辺上に柱がある場合は、min(M, N)個の領域に分割され、それ以外の場合はmin(M, N)+1個の領域に分割される。鳩ノ巣原理より、十分照明数の上界がこれらの領域の数と等しくなる。
長方形に柱を一つ：下界
下界を示すためには具体的な配置方法を与えればよい。
短辺上にある場合は、前回と同様、柱の位置を基準として周期境界で斜めに並べていけば良い（図４）。
短辺上にない場合は、柱の（長辺方向の）両隣に照明を置くことができる。これによって、(M-1, N-2)に帰着できる（今は、短辺をMとしている）。この方針でM+1の配置が作れそうだが、心配としては、①MとNが近い場合と、②Mが小さい場合の２つがある。
①MとNが近い場合、特にM=Nの場合は、図５のように両隣に照明を置いて削ると、短辺と長辺が逆転してしまう。そこで、正方形の場合は下の図６のように柱の四方に置く（正方形の場合で柱が短辺上にない、というのは、柱が辺の上にないということなので、このような照明の配置が常に可能である）。
②Mが小さい場合について、これまであまり正確に触れてこなかったが、私はとりあえずMが2以上の場合を想定している（M=1は自明のため）。上の説明で怪しいのは、M=2とM=3あたりだろうと思われる（このあたり、毎度ながら怪しい議論で申し訳ない）。ざっと確認したところ、大丈夫そうである。
ここまでのまとめ
ここまでの結果を表にまとめる。
全体的に議論が甘いので、誤りがある可能性があることを断っておく。
次の記事：照明 (3) - pzdcの雑記
