照明 (8)

これまで、美術館の照明の数について、7回にわたって考えてきた。今回、唐突に進展があったので、記事にしている。

きっかけ

先日、ひとりにしてくれに関する論文を読んだ。

"Hitori Numbers" Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa, Takeaki Uno, Journal of Information Processing, vol. 25, pp. 695-707 (2017) https://doi.org/10.2197/ipsjjip.25.695

この論文では、正方形盤面のひとりにしてくれで使用できる数の種類の総数の最小値と最大値について、それぞれ下界と上界を示している。結果は一見して非自明だが、証明は私にも理解できるものだった。こういった非自明な結果が、比較的単純な不等式を組み合わせることで出てくることに個人的に感銘を受けた。そこで、美術館の照明の個数についても、同じ要領で不等式を組み合わせていったら、欲しい上界・下界が私でも得られるのではないか、と考えた。

示したい不等式

今興味があるのは、階段型とでも呼ぶべきポリオミノの必要照明数である。図1と図2に、2タイプの形状クラスの結果をまとめる(この図は、一部は解析的に、一部は数値的に求めた結果である)。

図1 double-stairs型の必要照明数

図2 slided-rectangle型の必要照明数

これらの階段型に対する必要照明数は、部分的にしか示されていない。可能なら、全ての(w, h)に対して、解析的に答えを得たい。

特に欲しいのは、これらの必要照明数の下界である。図を見ていると、見通しが良さそうなのは、slided-rectangleの方である。wを固定した時の、hに対する増加の仕方を、図3と図4にプロットした。

図3 slided-rectangle, w=3の必要照明数のh依存性

図4 slided-rectangle, w=4の必要照明数のh依存性

図3と図4を見ると、どちらも 2h/3 以上になっていることがわかる。そこで、この下界を示すことを目標にしよう、と考えた。必要照明数をNと書くことにすると、今回示したい式は、

である。

最初の試み:コーナーの回収

最初に考えたのは、コーナーの回収である。

図5 コーナーの回収に必要な数の評価

階段型を考えるときに、照明がたくさん必要になるのはなぜか?と考えると、コーナー(図5の赤と青のマス)がたくさんあるから、というのが一つの理由と言えるだろう。ここから示せないだろうか。

一つの照明は、最大で4つのコーナーを照らすことができる。(w, h)盤面の場合、コーナーは2h個あるため、照明の数は

となることがわかる。一つの下界が得られたということで進歩だが、まだまだ下界としては不十分である。

クロス数と照射マス数

照明の数をなるべく少なくする限界について考えているのだから、ひとつひとつの照明の「効率」をよくする限界を考えれば良いだろう。どのように照明の効率を測れば良いだろうか。

図6 クロス数

図6では、複数の照明によって照らされるマスを赤色で塗っている。このように、一つのマスが複数の照明から照らされるのは、効率が悪そうだ。このような交差が起こるマスの個数を「交差数」と呼び、 C で表すことにする(例えば図6の場合はC=23)。

図7 照射マス数

次に、一つの照明に注目したときに、なるべくたくさんのマスを照らしてくれた方が嬉しい。例えば図7の左上の照明は9マスしか照らしていないが、右下の照明は11マス照らしている。そこで、照射するマスの個数の平均値を「平均照射マス数」と呼び、|L|で表すことにする(例えば図7の2つの照明に関して言えば、|L|=10)。

こうして定義した二つの量(Cと|L|)を使用すると、次の等式が書ける。

ここで、Sは盤面の面積である。Sは明らかにwhと等しい。ここから行うことは、Cの評価と|L|の評価である。今はNの下界が欲しいため、Cの下界と|L|の上界を考えれば良いだろう。

平均照射マス数 |L| の評価

照明は、基本的には、(2w-1)個のマスを照射することが分かる(図8)。

図8 平均照射マスの荒い評価

しかし、この評価は荒く、例外がある。具体的には、上辺を照射する場合と、下辺を照射する場合と、その両方を照射する場合に、照射マスが少なくなる。つまり、照明で上辺・下辺を照らすのは照明効率の点でロスになるわけである。この例外がどの程度効いてくるかは現段階では不明だが、少なくとも2w-1以下になるということはわかる。今は上界が欲しいだけなので、ここはとりあえずは詰めなくても良いだろう。上界は、

と書ける。

交差数 C の評価

交差は、2つの照明によって引き起こされる。今考えているのは正方格子なので、3つ以上の照明から出る光線が1点で交差することはない。ある照明aが作る交差の数を、その照明の「交差寄与数」と呼び、ca で表すことにする。すると、各交差は照明からの寄与としてダブルカウントされているため、

と書ける。ここで、和は全ての照明に対する和を表している。

今は交差数の下界が知りたいので、各照明の交差寄与数の下界を考えれば良いだろう。

図9 照明を起点に定義されるL、R、U、D

一つの照明に注目する。その照明から4方向に光線が出て、盤面が4つの象限に分断される。そのうち、左下の空間内のコーナーマス集合をL、右上の空間内のコーナーマス集合をRと書くことにする(図9)。また、光線が衝突する4つのマスを基準にして、U点とD点も定義する(図9)。いくつかの「例外」のケースを除けば、L側の空間とR側の空間は階段のような形になり、U点とD点は注目している照明に照らされない。ここで、「例外」には次の2つがある(両方の例外に該当するケースもあり得る)。

  • 例外1:照明が斜辺の近くにある
  • 例外2:照明が上辺もしくは下辺、またはその両方を照らしている。

今、いったんこの2つの「例外」のことを忘れることにする(つまり、例外でない照明の作る交差寄与数の評価を行う)。

L、R、U、Dに属するマスの総数は、w-1になることがわかるが、実はこのw-1個のマスを照らす照明の集合は、今考えている照明と必ずw-1個の交差を作る(図10~図14)。

図10 Rを照らそうとすると1回以上交差

図11 Dを照らそうとすると1回以上交差

図12 LとRを同時に照らそうとすると2回交差

図13 UとRを同時に照らそうとすると2回交差

図14 Rの2つを同時に照らそうとすると2回交差

よって、(例外に該当しないような照明の場合)交差寄与数の下界 w-1 が求まる。

次に例外を詰めていく。まず「例外1:照明が斜辺の近くにある」の方を考える。

例外1(照明が斜辺の近くにある場合)の交差寄与数

図15 端から1マスの場合

照明が端から1マスの距離にある場合(図15の場合)は、青いマスは結局、w-1 個あり、先ほどと同じように下界 w-1 が求まる。

図16 端から0マスの場合

照明が端から0マスの場合は、青いマスの個数がw-2になる。そして実際に、交差寄与数の下界は w-2 になる。

ここまでの結果をまとめよう。例外1まで考慮すると、交差寄与数は

と書ける。

ここで、wが小さい場合が怪しそうなので、確認しておく。caは定義より非負の値なので、w=1, w=2の時は上の不等式を満たしている。w=3の時は個別に考察すれば、ca≥1が確認できる。w=4以上は大丈夫そうだ。

ここまでの結果より、もし例外2を考慮しなくて良いなら

よって、

これはまさに欲しい結果だった。

さて、欲しい結果は得られたが、この証明は「例外2」を考慮していない。

例外2を詰める準備:三角不等式

これまでのやり方で例外2を詰めていくのは難しい様子である。数式にするのは複雑そうなので、妥協した不等式で抑え込むと、致命的に下界が下がってしまった。しかし、もっとうまい方法を見つけた。まず、美術館の盤面と必要照明数に関する三角不等式を示す。

図17 直線を挟んで二つの美術館をつなげる

図17のように、ある直線(縦線とする)を挟んで左右の二つの美術館を連結したとする。すると、いくつかの照明は一般には「矛盾」するだろう。どのように矛盾するかというと、点線で示したように、縦線を挟んで両側の照明が喧嘩する。喧嘩は、二つの照明が必ずペアになることによっておこる。つまり、3つ以上の照明が喧嘩することはない。照明の数を増やさずに、この喧嘩を平穏に解消する方法がある。

図18 喧嘩の解消

喧嘩している照明ペアの内、片方の照明を消すことを考える。すると、喧嘩度が1下がるが、代わりに、一般に照らされないマス集合が生じる。しかしながら、そのような不遇なマス達は、必ず縦一列に整列するため、不遇なマスの内の一か所に先ほど取り去った照明を入れ直せば、喧嘩度が1下がった状況を維持しつつ不遇なマスをなくすことができる(図18の場合、点線の丸を除去する代わりに、バツ印のマスに照明を入れればよい)。この手順を繰り返すことによって喧嘩度は強い意味で単調に減少していくため、最終的に解が構成される。この過程で照明の数は増加しないことに注意する。

以上から、美術館の直線を挟んだ連結は、必要照明数に関して三角不等式を満たしてくれることが分かる。

例外2を詰める準備:周期配置の場合

wを固定したまま、hを無限に大きくすることができる。その時に照明の配置を「周期的」に入れることができたとする。一つの照明が3つ以上の単位セルを照らす状況は少しややこしい。そこで、周期をn倍に解釈して、周期単位の(w, h)は、h≫wだと考える。こうすると、各照明はちょうど2w-1個のマスを照らす、という考え方や、交差寄与率がw-2以上である、という議論がそのまま適用できる。結果、単位セル(w, h)に含まれる照明の数は 2h/3 以上になることがわかる。

つまり、周期的な場合には所望の不等式が示せるのである。端があるのが厄介なのだった。

例外2を詰める

ある有限の(w, h)の構造で閉じている形を考える。この形に、照明数Nの解があると仮定する。この形を2つ連結して、(w, 2h)の形を作ることを考えると、既に示した三角不等式より、照明数2N以下の解が存在する。これを繰り返していくのだが、喧嘩をしないように照明を仲裁していく必要があるため、繰り返しをするたびにセルの中の照明の個数や配置が少しずつ異なってくると考えられる。しかし、マルコフ過程であることと、鳩ノ巣原理より、一定の有限回数繰り返したところで、完全な同一の照明配置に戻るだろう。つまり、この手順を繰り返す際に、照明の配置を周期的にすることができる。この時のセルの数をpとすると、(w, ph)の単位セルで周期的な配置が存在して、照明の数はpN以下になる。もしNが2h/3よりも小さかったとすると、(w, ph)の単位セルに2ph/w以下の照明の周期配置が存在することになって、これは周期配置の定理に矛盾する。

したがって、有限の(w, h)の場合であっても、必要照明数は 2h/3 以上であることがわかる。

これで完全に示せたと思うが、どこかに議論の穴があれば、ご指摘いただきたい。

ここまではslided-rectangle型に対する評価だったが、double-stairs型に対しても同様にして下界を与えることができる。

結果

まとめると、slided-rectangle型に対する下界は

であり、double-stairs型に対する下界は、

数値計算した範囲(図1、図2)で、これらの不等式を満たしていることを確認済みである。終わってみると、意外と簡単に示せたという印象である。