Aqre最小化問題

ほげ

 

問題

$ m \times n $  の盤面がある。盤面のマスのいくつかを黒く塗るとき、次をみたすように塗ったものを「Aqre 盤面」とよぶ：

  • 黒マスが連結している
  • タテにもヨコにも白マスが四連続しない
  • タテにもヨコにも黒マスが四連続しない

Aqre 盤面を構成するのに必要な黒マスの個数の最小値を求めよ。

 

下限について

必要な黒マスの個数が、盤面全体のおおよそ $\dfrac{2}{5}$ であることが示せる。最初に言及したのはおそらく utime 氏。

以下、正確な証明を残しておく。

 

記号について：

$ m \times n$ の Aqre 盤面に対し、$ B $ を黒マスの個数とする。

また、隣接するマスのペアを考え (i.e. グリッドグラフとしての辺)、黒マス 2 つのペアの個数・白マス 2 つのペアの個数・黒マスと白マスのペア (順不同) の個数を、それぞれ $ b $, $ w $, $ g $ とおく。

さらに、盤面の端と黒マスが接触している部分の個数を $ e $ とおく。

 

定理

次の不等式が成り立つ：

\[  5B \geq  2mn - 3m - 3n + 3e -3 \]

 

証明

まず黒マスの四辺に注目して、

\[ 4B = e + 2b + g \tag{1} \]

を得る。また、ペアの個数をカウントして

\[ w + g + b = 2mn - m - n  \tag{2} \]

がわかる。

 

ここで、ルールの制約による不等式評価を考える。

まず黒マスの連結性によって、次の式が成り立つ：

\[ B-1 \leq b \tag{3} \] 

次に白マス四連禁について。ひとつの列に注目して、黒黒・白白・黒白/白黒のペアの個数を $ b_i $, $ w_i $, $ g_i $ とおき、端と接続する個数を $ e_i $ とおく。

このとき、連続する白マスのブロックの個数は $ (g_i+2-e_i)/2 $ と数えられる。すると四連禁よりブロックごとに白マスのペアは $ 2 $ 個までしかないため、ブロックすべてを合わせて $ w_i \leq g_i  - e_i  + 2 $ と評価できる。これを各行各列について足し合わせると

\[ w \leq g - e + 2m + 2n  \tag{4} \] 

となる。

 $(3) \times 3 + (4) $ を考えると

\[  3B -3 + w  \leq 3b + g - e + 2m + 2n \]

となり、両辺に $ 5B $ を加えて整理すると

\[ 8B + w - 3b - g + e - 2m - 2n - 3 \leq  5B \]

となる。ここで $ (1) $ から、この左辺は

\[ 2(e+2b+g) + w - 3b - g + e - 2m - 2n - 3 = w + b + g - 2m - 2n + 3e - 3 \]

となり、また $ (2) $ から、

\[ w + b + g - 2m - 2n + 3e - 3 = 2mn - 3m - 3n  + 3e - 3 \]

となる。よって定理の式が示された。(証明終)

 

定理の式および、$ e $ のオーダーが $ o(m+n) $ であることから、黒マスの個数がおおよそ $ 2mn/5 $ であることがわかった。

 

なお、この証明では黒マス四連禁を使用していないことに注意する。

それに伴い、黒マス四連禁以外の二条件をみたすように塗ったものを「準 Aqre 盤面」とよぶことにする。上の注意により、準 Aqre 盤面についてもこの定理が成立する。

 

誤差項について

上の証明の $ (3) $ の評価において、両辺の差分は黒マスのなすループ (穴) の個数である。これを $ H $ とおく。(すなわち $ b = B + H - 1 $ である。)

また $ (4) $ の評価における両辺の差分は、白マスのブロックの長さに起因するものである。長さ $1$, $2$ の白マス区間の個数をそれぞれ $I_1$, $I_2$ とおく。このとき差分は $ 2 I_1 + I_2 $ となる。

最終的に得られた評価は $ (3) \times  3 + (4) $ から得たものなので、その誤差は $ 3H + 2I_1 + I_2 $ となる。

 

定理の系

\[ 5B = 2n^2 - 3m - 3n + 3e - 3 + 3H + 2I_1 + I_2 \]

 

また $ e $ について、辺の列の四連禁から $ e \geq 2 \lfloor \frac{m}{4} \rfloor + 2 \lfloor \frac{n}{4} \rfloor $ となっている。これを用いると $ B $ の下限を $ m, n $ のみの式で表すことができるが、その場合の誤差については、上のものに加えて端のロスの $ 3 $ 倍が追加されることに注意する。最適な端の状態からのロスを $ L $ とおき、$ P = 3H + 2I_1 + I_2 + 3L $ をペナルティ項とよぶことにする。

 

ここからいくつか例をあげる。わかりやすさのため、$ m = n $, すなわち正方形盤面を扱うことにする。

この場合、定理および $ e $ の評価により、$ 5B \geq 2n^2 - 3n - 3 - 3r $ となる。(ただし $ r $ は $ n $ を $ 4 $ で割った余り)

 

1. $ n = 7 $ の場合

$ 5B  \geq 2n^2 - 3n - 12 = 65$.  ここで $ B=13 $ に対応する準 Aqre 盤面が次の図である：

 

f:id:SP1_puzzle:20201114133816p:plain

ペナルティ項が全くない盤面だが、$ n $ が小さい場合特有の現象でもある。

これが Aqre 盤面になると 、黒マス四連禁のせいでペナルティ項なしの構成はできない。実は「周長」 $ e + g  = 4B - 2b = 2B - 2H + 2 $ についての精密な議論により、$ B=15 $ が最小なことが示せる。

実際、行方向全体で黒マスのなすブロックは少なくとも $ 8 $ 個必要で (i.e. $ 7 $ 個 だと足りない) 、列方向についても同じなので、周長が $8\times 4 = 32 $ 以上となるためである。

加えてこの評価の誤差を吟味することで、このサイズの Aqre 盤面は、回転・裏返しをのぞいて次の一通りしかないと分かる：

この図では $ H = 0 $, $ I_1 = 2$, $ I_2 = 6 $, $ L = 0 $ なので $ P = 10 $ である。これは 評価式の誤差 $ 15\times 5 - 65 $ と一致している。 

 

2.  $ n = 11 $

$ 5B \geq 2n^2 - 3n - 12 = 197 $. $ B=40 $ に対応する準 Aqre 盤面は以下の通り：

 

f:id:SP1_puzzle:20201114133852p:plain

ループがちょうど一つあるので、その分の誤差 ($ P =  1\times  = 3 $) が出ている。

 

Aqre 盤面については計算機によって $ B=47 $ が最小なことが示されている (semiexp氏)。構成は以下の通り (わんど氏) ：

 

3. $ n = 8 $

$ 5B \geq 2n^2 - 3n - 3 = 101 $ だが、Aqre 盤面の最小は $ B= 27 $ である。準 Aqre 盤面の最小もおそらく $ B = 27 $ と思われる：

 

この図では $ H = 2 $, $ I_1 = 9$, $ I_2 = 10 $, $ L = 0 $ であり、$ P = 34 $ となる。これは 評価式の誤差 $ 27\times 5 - 101 $ と一致している。

 

これらの例からわかる通り、定理の評価はあくまで二次項までの評価に過ぎず、ペナルティ項がそれなりに大きくなってしまう。そしてその実際の値がわからないために、正確な最小値はよく分からない、というのが現状である。正確な評価のためには別の手段が必要そうである。

なお、小さいケースについては計算機を用いて最小値が求まっているが (わんど氏・semiexp 氏)、一般の場合について計算するのは困難なようである。

 

誤差項の言いかえ

 

$ 2 I_1 + I_2 $ という項は別の言いかえができる。

各行各列で白マスのなす区間の個数を考え、その総数を $ I_W $ とおく。このとき、$ 2 I_1 + I_2 = 3I_W - 2(mn - B) $ であることが示せる。なお $ mn - B $ は白マスの個数である。

これを定理の系に代入して整理すると、次の式となる：

\[ B = I_W + H + e - m - n - 1 \]

これは目新しい式というわけではなく、単に黒マスの連結性に応じて周長を列ごとにカウントして出てくる式で、黒白四連禁に関係なく出てくるはずである。

$ I_W $ をどう評価するのが難しいのであまり解決になっていないが、この式自体は今後似たような連結性がらみの議論で使えるかもしれない。

 

追記

すでにまり餡氏が言及していた...

 ま、いっか