超超へやわけMX：
https://scrapbox.io/nishinanntoka/%E8%B6%85%E8%B6%85%E3%81%B8%E3%82%84%E3%82%8F%E3%81%91MX
コンピューターを用いた探索により、$L$ が小さい場合に角 $5\times L$ に入る黒マスの最大値が求められている。
https://scrapbox.io/nishinanntoka/%E3%81%B8%E3%82%84%E3%82%8F%E3%81%91DP
以下は一般の $L$ についての結果を考察したもの。$L = 16m$ と表される場合について、タイトな上界を求める。
補題
Lemma (Corollary of Tobo Theorem)
辺の $2\times L$ に黒マスを $C$ 個入れたとする。盤面端に接している行に入る黒マスの個数を $r$ とすると、$r \leq L-C+1$ が成り立つ。
証明
盤面端に接していない方の行に入る黒マスの個数を $s$ とおく。$2r+s-L \leq 1$ を示したい。
$L$ についての帰納法。$L=1, 2, 3, 4$ について成り立つことは確認できる。$L \leq 5$ のときは右端から黒マスのパターンを考えることで、$L$ が小さいケースに帰着できる。■
参考リンク：https://docs.google.com/document/d/1WW2WKuCNrakIXDomgt5onrL38H1FAWU0onLa-3KXF0M/edit#
表題の証明
$L=16m$ のときに角 $5 \times L$ に黒マスが $29m$ 個までしか入らないことを示す。なお、へやは左が $5$ の辺で盤面端、下が $L$ の辺で盤面端とする。
黒マスが $29m+1$ 個入ったとする。
ペナルティ理論によると、へやのペナルティの全体許容値は
- ループ＋ハーフループで $80m$
- 角で $8m+3$
の合わせて $88m+3$ である。よって許容されるペナルティは、そこから $3\times (29m+1)$ を引いた $ m $ である。
なお、角のペナルティについて正確には、
- 左上マスに入らないと $1$ ペナ
- 左辺の 左上を除く $4$ マスをとなり同士 $2$ 個ずつペアにしたとき、ペアの両方が白だと $1$ ペナ
- 下辺 $16m$ マスをとなり同士 $8m$ 個ずつペアにしたとき、ペアの両方が白だと $1$ ペナ
と記述できる。
ここで、上辺のハーフループおよび左上マスで $1$ ペナルティ消費するとわかる。
また空中の $3\times 4$ に黒マスが $5$ 個しか入らないため、盤面の上 $3$ 行に黒マスは最大 $20m$ 個しか入らない。
よって、盤面の下 $2$ 行に $9m+1$ 個入れる必要がある。
すると上記の補題より、盤面端に接している行に黒マスは $7m$ 個までしか入らない。
したがって、下辺でペナルティを生み出すペアが少なくとも $ m $ 個ある。
以上よりペナルティが $m+1$ 以上あるとわかり、許容値の $ m $ を超えるため矛盾。
コメント
$29m$ 個入れるための具体的な構成として、辺の $5\times 15$ に $29$ 個入れるものを並べていく、というものがある。
わかりやすさのために $L$ を $16$ の倍数としたが、余りがある場合でも同様の議論が可能。
