MX値2

白マスどうしがタテヨコに接している時、その境界を「継ぎ目」と呼ぶことにする。
継ぎ目の数が白マスの数に対して少なすぎると、白マスはひとつながりにならず、分断禁に反していしまう。
ひとつながりならば、継ぎ目の数≧白マスの数-1 でなければならない。

この不等式から、黒マスの数の上界が得られる。


角のへや nxm

((2n+1)(2m+1)+k)/12
ただし、k=3(n,mが奇数),1(n,mが奇数と偶数),-1(n,mが偶数と偶数)

角p4では、多くのn,mでこれがそのままMX値となることを示しています。

導出方法を以下に示す。nが奇数、mが偶数の場合を考える(他の場合もほぼ同じ議論になる)。
角のへやを、盤面の外壁がない方向に1マスずつ拡大した(n+1)(m+1)マスを考える。
黒マスが無ければ、(n+1)(m+1)マスの白マスが(n(m+1)+(n+1)m)本の継ぎ目で連結されている状態である。
ここに、継ぎ目の数をあまり減らさないように黒マスを入れていく。ただし、へやの中のみに黒マスを入れる。
角のマス(1マスのみ)、辺のマス(盤面の外壁に接するn-1+m-1マス)、それ以外のマスに黒マスを1つ入れると、減る継ぎ目の数はそれぞれ2,3,4本である。
いま、黒マスをp個入れるとする。
継ぎ目の数を減らさないために、角や辺のマスに最大限の数の黒マスを入れたい。
よって、黒マス隣接禁を考慮すると、
角:1個
辺:(n-1)/2+(m-2)/2 個 黒マスを入れることになる。
残りの黒マスはそれ以外のマスに入れる。
a=1, b=(n-1)/2+(m-2)/2 とすれば、残る継ぎ目の数は、
(n(m+1)+(n+1)m)-(a*2+b*3+(p-a-b)*4)
となる。
よって、継ぎ目の数≧白マスの数-1 より、pは以下の不等式を見たす必要がある。
(n(m+1)+(n+1)m)-(a*2+b*3+(p-a-b)*4)(n+1)(m+1)-p-1
これを整理して上記の上界を得る。

辺のへや nxm 辺に接する方をnとおく。

((n+1)(2m+1)+k)/6
ただし、k=0(nが奇数),-1(nが偶数)

空中のへや nxm

((n+1)(m+1)+k)/3
ただし、k=-1(n,mが奇数),-3(nmが偶数)

nxmのへやを上下左右に1マスずつ拡大した(n+2)(m+2)マスを考える。
黒マスが無ければ、(n+2)(m+2)マスの白マスが(n+1)(m+2)+(n+2)(m+1)本の継ぎ目で連結されている状態である。
ここに黒マスを1個入れると、白マスは1個減少し、継ぎ目は4本減少する。
また、黒マスをp個入れると、白マスはp個減少し、継ぎ目は4p本減少する。(黒マスは隣接しないため)
よって、継ぎ目の数≧白マスの数-1 より、pは以下の不等式を満たす必要がある。
(n+1)(m+2)+(n+2)(m+1)-4p≧(n+2)(m+2)-p-1
これを整理して上記の上界を得る。
またへやの一辺が偶数のときは、等号は成立しえないため、上界を下げることができる(詳細略)。

四方を壁に囲まれたへや nxm

(nm+k)/3
ただし、k=3(n,mが奇数),2(n,mが奇数と偶数),1(n,mが偶数と偶数)

このうち、n=mのとき、いくつかのnでMX値が示されています。
黒マス最密充填のはなし 2020-04-05(SP1さん)
具体的な黒マスの埋め方は上記を参照ください。
MX値は、
・0, 3 mod 6 のとき n^2 / 3 個 (例外として、n=3のとき、4個)
・2, 4 mod 6 のとき (n^2 - 1) / 3 個
・1, 5 mod 6 のとき (n^2 +2) / 3 個
となります。
3 mod 6のときのみ、上界は(n^2/3)+1個ですが、n=3を除き、この詰め方は不可能です。
(この詰め方の時、不等式の両辺が等しくなり(継ぎ目の数=白マスの数-1)、さらに外周のマス(盤面の四辺のうちいずれかと辺を共有するマス)に最大限黒マスを入れる必要があります。しかし、この黒マスの入れ方では、n>3のとき、盤面外周のひとつ内側全体を一周する白マスのループが生じてしまいます。この場合、”継ぎ目の数=白マスの数-1”を満たせません。)

つまり、n=mのときは、n≡3 (mod 6) (n>3)を除き、不等式から得られる上界の小数点以下を切り捨てた値がMX値と等しくなります。



角のへやについて、
プログラム探索によるMX値と、
((2n+1)(2m+1)+k)/12
ただし、k=3(n,mが奇数),1(n,mが奇数と偶数),-1(n,mが偶数と偶数)
この式で得られる上界の差を取りました。

へやわけ角のへやのMX値と上界の差(Googleスプレッドシート)

へやの一辺が2や3のものは、へやのサイズが大きくなるほど、差が大きくなっています。
この式では、へやが細長い長方形になればなるほど、上界とMX値の差が広がってしまうようです。

手筋集に戻る




このサイトは無料ホームページ作成.comで作成されています