ペナルティへやわけ
白マスどうしがタテヨコに接している時、その境界を「継ぎ目」と呼ぶことにする。
継ぎ目の数が白マスの数に対して少なすぎると、白マスはひとつながりにならず、分断禁に反してしまう。
ひとつながりならば、継ぎ目の数>=白マスの数-1 でなければならない。
この不等式から、黒マスの数の上限が得られる。
四方を壁に囲まれたへや nxm
(mn+k)/3
ただし、k=3(n,mが奇数),2(n,mが奇数と偶数),1(n,mが偶数と偶数)
導出方法を以下に示す。例としてnとmがともに偶数の場合を考える（他の場合もほぼ同じ議論になる）。
黒マスが無ければ、mnマスの白マスが(n(m-1)+(n-1)m)本の継ぎ目で連結されている状態である。
n=m=10 のとき、継ぎ目(白丸)の数は90+90=180本。
ここに、継ぎ目の数をあまり減らし過ぎないように黒マスを入れていく。
マスを3種類に分類する：
角のマス(4マスのみ)…黒マスを入れると継ぎ目が2本減る。
辺のマス(角のマスを除く外周のマス、2*(n-1+m-1)マスある)…継ぎ目が3本減る。
それ以外のマス…継ぎ目が4本減る。
https://gyazo.com/953d75df4160c91bf2404ae0b08d44e3
白丸および黒丸は継ぎ目で、黒マスを置いたために減った継ぎ目を黒丸で表した。残り97マスの白マスが、180-(2+3+4)=171本の継ぎ目でつながっている。
いま、黒マスを全部でp個入れるとする。
継ぎ目の数を減らしすぎないために、角や辺のマスに最大限の数の黒マスを入れたい。
よって、黒マス隣接禁を考慮すると、
角：4個
辺：2*((n-4)/2+(m-4)/2)個 黒マスを入れることになる。n=10, m=10のとき、3+3+3+3=12個
残りの黒マスはそれ以外のマスに入れる。
a=4, b=2*((n-4)/2+(m-4)/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)>=nm-p-1 (a=4, b=2*((n-4)/2+(m-4)/2))
これを整理して、(mn+1)/3>=p を得る。
n=10,m=10のとき、101/3>=p、(33+2/3)>=p。p=33のとき、角4マス、辺12マス、その他17マスの黒マスを入れると
継ぎ目の数：180-2*4-3*12-4*17=68
白マスの数-1：100-33-1=66
https://gyazo.com/e2d24b0b4849bd9d03e80bca541f4c1a
33個入れることができた。
ペナルティへやわけ
ここで、緑のループが2つある。
上は白2x2にあり、白マスが4マス、継ぎ目が4つになっている。白マス4マスをひとつながりにするためには継ぎ目は3つで十分なのに、白2x2があるせいで継ぎ目を1つ損している。
下はもう少し大きいループ。白マス8マスをひとつながりにするために継ぎ目を8つ使っており、白マスのループがあるせいで継ぎ目を1つ損している。
継ぎ目の数：180-2*4-3*12-4*17=68 と、白マスの数-1：100-33-1=66 の差68-66=2は、この2つの損に対応している。
これをペナルティと呼ぶ。
10x10の盤面に33個の黒マスを入れるとき、以下のペナルティが生じる場所がちょうど2ヶ所だけ生じる。
白マスループ1つにつき、ペナルティ1
白2x2 1つにつき、ペナルティ1
アースされていない黒マス集団1つにつきペナルティ1/白マスに囲まれた格子点1つにつきペナルティ1 と考えるとより正確である。たとえば、白2x4があるとき、ペナルティ3。2x4からなるループを計上する必要はない。実際、白2x4=8マスを繋ぐのに継ぎ目を10本使っているので、3本多い。
角4マス、辺12マス、空中17マスから変化するとペナルティが発生。
角3, 辺13, 空中17 -> ペナルティ1
角4, 辺11, 空中17 -> ペナルティ1
n=10, m=10のとき (33+2/3)>=pであった。この2/3の部分が、許容されるペナルティの数が2であることと対応している。
n=mのとき、いくつかのnでMX値が示されています。
具体的な黒マスの埋め方は上記を参照ください。
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のとき、盤面外周のひとつ内側全体を一周する白マスのループ(ペナルティ)が生じてしまいます。)
つまり、n=mのときは、n≡3 (mod 6) (n>3)を除き、不等式から得られる上界の小数点以下を切り捨てた値がMX値と等しくなります。
角のへや nxm
((2n+1)(2m+1)+k)/12
ただし、k=3(n,mが奇数),1(n,mが奇数と偶数),-1(n,mが偶数と偶数)
導出方法を以下に示す。例として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
これを整理して以下の上界を得る（上記と同じ）。
((2n+1)(2m+1)+k)/12
ただし、k=3(n,mが奇数),1(n,mが奇数と偶数),-1(n,mが偶数と偶数)
角のへや_具体的構成2では、上界が整数となるとき、ペナルティをどうしても0にできないため、(上限-1)=MX値となることを示しています。 いずれにせよ、角のへやでは、一辺が4以上のとき、ペナルティは1,2,3のいずれかになります。
辺のへや 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
これを整理して上記の上界を得る。
またへやの一辺が偶数のときは、等号は成立しえないため、上界を下げることができる（詳細略）。